783. Count the Fastest Routes
A delivery drone moves through a district of n checkpoints numbered 0 to n - 1, using one-way corridors roads[i] = [from, to, minutes]. No two corridors share the same ordered pair of checkpoints, and no corridor starts and ends at the same checkpoint. The drone starts at checkpoint 0 and must reach checkpoint n - 1.
Count the distinct checkpoint sequences that reach the destination in the minimum possible total time. Return the count modulo 1000000007. If the destination cannot be reached, return 0; if n = 1 the drone is already there and the answer is 1.
Example 1
- Input:
- n = 5roads = [[0,1,2],[0,2,2],[1,3,3],[2,3,3],[3,4,1],[0,4,9]]
- Output:
- 2
- Explanation:
The fastest time is 6 and only the routes 0-1-3-4 and 0-2-3-4 achieve it; the direct corridor 0-4 takes 9, so the count is 2.
Example 2
- Input:
- n = 3, roads = [[0,1,5]]
- Output:
- 0
- Explanation:
Checkpoint 2 has no incoming corridor, so the destination is unreachable and the answer is 0.
Example 3
- Input:
- n = 4, roads = [[0,1,1],[0,2,2],[1,2,1],[1,3,3],[2,3,2]]
- Output:
- 3
- Explanation:
Every route to checkpoint 3 takes at least 4 minutes: 0-1-3 (4), 0-1-2-3 (4) and 0-2-3 (4) all tie, giving 3 routes.
Constraints
- 1 ≤ n ≤ 105
- 0 ≤ roads.length ≤ 2 * 105
- 0 ≤ from, to < n, from ≠ to, and each ordered pair appears at most once
- 1 ≤ minutes ≤ 104
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 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O((n + m) log n)
- Space
- O(n + m)