1081. Bottleneck Routes
A freight company runs trucks between n depots numbered 0 to n-1. Each entry edges[i] = [u, v, w] describes a two-way road between depots u and v that trucks weighing at most w tons may use. A truck can drive any route, and the heaviest truck that fits a route is limited by the weakest road on it.
Each query queries[j] = [a, b] asks for the heaviest truck that can get from depot a to depot b when the best route is chosen. Return an array ans where ans[j] is that maximum weight. If a == b, no road is needed and the answer is 0. If no route exists, the answer is -1.
Several roads may join the same pair of depots, and a road may even start and end at the same depot.
Example 1
- Input:
- n = 5edges = [[0,1,7],[1,2,4],[0,2,3],[2,3,9],[3,4,2]]queries = [[0,2],[0,4],[3,1],[4,4]]
- Output:
- [4,2,4,0]
- Explanation:
Depots 0 and 2 can use the direct road (limit 3) or go through depot 1 (limits 7 and 4), so the best limit is 4; the only way to depot 4 ends with the road of limit 2, and a query from a depot to itself gives 0.
Example 2
- Input:
- n = 4edges = [[0,1,5],[2,3,8]]queries = [[0,3],[2,3],[1,0]]
- Output:
- [-1,8,5]
- Explanation:
The network has two separate islands, so the first query has no route at all and gets -1, while the other two are single roads.
Example 3
- Input:
- n = 3edges = [[0,1,2],[0,1,6],[1,2,6],[1,2,1]]queries = [[0,2],[2,0]]
- Output:
- [6,6]
- Explanation:
Only the strongest of the parallel roads matters on each leg, so both directions travel over two roads of limit 6.
Constraints
1 ≤ n ≤ 105
0 ≤ edges.length ≤ 2 * 105, edges[i] = [u, v, w] with 0 ≤ u, v < n and 1 ≤ w ≤ 109
1 ≤ queries.length ≤ 105, 0 ≤ a, b < n
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 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O((m + q) log n)
- Space
- O(n + m)