782. Most Reliable Route
A mesh of n radio towers numbered 0 to n - 1 is joined by two-way links. Link edges[i] = [a, b] delivers a message in either direction and succeeds with independent probability prob[i]. A message hopped along a chain of links is delivered only if every link succeeds, so the delivery chance of a route is the product of its link probabilities.
Return the largest delivery probability among all routes from tower start to tower end, or 0.0 if the two towers are not connected. Answers within 1e-6 of the true value are accepted. Links with probability 0 never help, and several links may join the same pair of towers.
Example 1
- Input:
- n = 4edges = [[0,1],[1,2],[0,2],[2,3]]prob = [0.9,0.8,0.5,0.5]start = 0end = 3
- Output:
- 0.36000000000000004
- Explanation:
Going 0-2-3 succeeds with 0.5 * 0.5 = 0.25, while 0-1-2-3 succeeds with 0.9 * 0.8 * 0.5 = 0.36, which is the best.
Example 2
- Input:
- n = 4edges = [[0,1],[2,3]]prob = [0.7,0.4]start = 0end = 3
- Output:
- 0
- Explanation:
Towers 0-1 and towers 2-3 form two separate pairs with no link between them, so no route from tower 0 to tower 3 exists and the probability is 0.0.
Example 3
- Input:
- n = 3edges = [[0,1],[1,2],[0,2]]prob = [0.95,0.95,0.8]start = 0end = 2
- Output:
- 0.9025
- Explanation:
The two-hop route succeeds with 0.95 * 0.95 = 0.9025, beating the direct link at 0.8.
Constraints
- 2 ≤ n ≤ 104
- 0 ≤ edges.length = prob.length ≤ 5 * 104
- 0 ≤ a, b < n and a ≠ b
- 0 ≤ prob[i] ≤ 1, given with at most 5 decimal places
- 0 ≤ start, end < n and start ≠ end
How this problem is judged
- Answers
- Numbers are accepted within a tolerance of 1.0E-6: |answer - expected| <= 1.0E-6 x max(1, |expected|).
- Tolerance
0.000001- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O((n + m) log n)
- Space
- O(n + m)