Count Fastest Routes
MediumAdvanced Graphs
Problem
A city has n intersections and two-way streets streets[i] = [u, v, minutes]. A ride-share app wants to know how many different routes from intersection 0 to intersection n - 1 take the minimum possible time.
Two routes are different if their sequences of streets differ. Return the count modulo 10^9 + 7.
Example 1
- Input:
- n = 4, streets = [[0,1,1],[0,2,1],[1,3,1],[2,3,1]]
- Output:
- 2
0 → 1 → 3 and 0 → 2 → 3 both take 2 minutes.
Example 2
- Input:
- n = 2, streets = [[0,1,5]]
- Output:
- 1
Example 3
- Input:
- n = 4, streets = [[0,1,1],[1,3,1],[0,3,2],[0,2,1],[2,3,2]]
- Output:
- 2
0 → 1 → 3 and the direct street both take 2; 0 → 2 → 3 takes 3.
Constraints
- 1 ≤ n ≤ 10^4
- n - 1 ≤ streets.length ≤ 2·10^4
- 1 ≤ minutes ≤ 10^6
- Intersection n - 1 is reachable from 0.
Hint
Show the first hint
Dijkstra gives you the minimum time. How can you count the ways to achieve it at the same time?
Walkthrough
How to approach it
01Clarify before coding
- Can streets have zero length? No, at least 1 minute, which keeps the counting order safe.
- Can two streets join the same intersections? Yes, and they are different routes.
- Why the modulo? The number of routes can grow exponentially (2^40 in a ladder of diamonds).
02Brute force
Enumerate every path from 0 to n - 1, compute its time, and count the ones that match the minimum.
Cost: Exponential: a chain of k diamonds already has 2^k shortest routes.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.