765. Weakest Link Route
A courier company runs n depots numbered 1 to n. Each entry [a, b, rating] of roads is a two-way road between depots a and b whose roughness is rating (a larger number means a rougher road). Several roads may join the same pair of depots.
A trip starts at depot 1 and ends at depot n. It may pass through depots and reuse roads as many times as it likes. The comfort floor of a trip is the smallest rating among the roads it uses. Among all possible trips, return the smallest comfort floor that any of them can have. The input guarantees that at least one trip from depot 1 to depot n exists.
Example 1
- Input:
- n = 5roads = [[1,2,9],[2,3,4],[3,5,7],[4,5,2],[1,5,12]]
- Output:
- 2
- Explanation:
The walk 1-5-4-5 crosses the road 4-5 of rating 2, and no rating is lower, so the answer is 2.
Example 2
- Input:
- n = 6, roads = [[1,2,6],[2,6,3],[3,4,1],[4,5,2]]
- Output:
- 3
- Explanation:
Only the roads 1-2 and 2-6 can be touched by a walk starting at city 1; the cheap roads 3-4 and 4-5 are in another region, so the answer is 3.
Constraints
- 2 ≤ n ≤ 105
- 1 ≤ roads.length ≤ 105
- 1 ≤ a, b ≤ n and a ≠ b
- 1 ≤ rating ≤ 104
- Depot n is reachable from depot 1.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O((n + m) * alpha(n))
- Space
- O(n)