790. Weight-Limited Paths
A warehouse robot moves between n waypoints numbered 0 to n - 1. Each entry [u, v, w] in edges is a two-way corridor between u and v with toll w. Several corridors may join the same pair of waypoints.
Each entry [p, q, limit] in queries asks whether the robot can get from waypoint p to waypoint q using only corridors whose toll is strictly less than limit; the robot may pass through other waypoints and reuse corridors. If p == q the robot is already there and the answer is true. Return an array of booleans where entry i is the answer to queries[i]. Queries are independent of each other.
Example 1
- Input:
- n = 4edges = [[0,1,3],[1,2,5],[2,3,2],[0,3,9]]queries = [[0,2,6],[0,2,5],[0,3,10]]
- Output:
- [true,false,true]
- Explanation:
Limit 6 allows corridors 0-1, 1-2; limit 5 drops 1-2 so 0 and 2 are split; limit 10 allows every corridor.
Example 2
- Input:
- n = 3edges = [[0,1,4],[0,1,1]]queries = [[0,1,2],[1,2,100],[2,2,1]]
- Output:
- [true,false,true]
- Explanation:
The cheap parallel corridor of price 1 works for limit 2, station 2 has no corridors so it only reaches itself.
Constraints
- 1 ≤ n ≤ 105
- 0 ≤ edges.length, queries.length ≤ 105
- 0 ≤ u, v, p, q < n
- 1 ≤ w, limit ≤ 109
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 300 msC++ 75 msJava 150 msJavaScript 150 msTypeScript 150 ms
Expected complexity
- Time
- O((m + q) log(m + q))
- Space
- O(n + q)