Number of Ways to Arrive at Destination
You are in a city that consists of n intersections numbered from 0 to n - 1, connected by bidirectional roads. Each road roadsi = [u, v, time] takes time minutes to travel between u and v. Return the number of ways to travel from intersection 0 to intersection n - 1 in the shortest possible amount of time, modulo 109 + 7. Run Dijkstra from node 0, but also track a ways count per node: when a shorter time is found, reset the count to the predecessor’s count; when an equally short time is found, add to it.
Constraints
- 1 ≤ n ≤ 200
- n - 1 ≤ roads.length ≤ n * (n - 1) / 2
- roadsi.length == 3
- 0 ≤ ui, vi ≤ n - 1
- 1 ≤ timei ≤ 109
- ui != vi
- It is guaranteed that intersection n - 1 is reachable from intersection 0
Example
Input
n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]Output
4Explanation There are four different routes from intersection 0 to intersection 6 that all take the same minimum amount of time.
In plain terms
- Ways count
- How many distinct shortest-time routes reach a given node — not just the shortest time itself.
Track time and ways-to-reach together as you pop each node
00 · 1
1∞ · 0
2∞ · 0
Statusinit
Start at node 0: time 0, 1 way to be here.
What happens in this step
dist[0] = 0, ways[0] = 1 dist[1] = dist[2] = ∞, ways[1] = ways[2] = 0 Node 0 starts at time 0 with exactly 1 way to be there — standing still. Every other node is unreached.
Step 1 of 4
Steps to visualize
- Set node 0 to time 0 with 1 way to be there; every other node starts at infinity with 0 ways.
- Repeatedly pop the unfinalized node with the smallest time.
- Relaxing a neighbor with a strictly shorter time resets its ways count to the popped node’s ways.
- Relaxing a neighbor with an equally short time adds the popped node’s ways to its own.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
00 · 1
1∞ · 0
2∞ · 0
Statusinit
Start at node 0: time 0, 1 way to be here.
What happens in this step
dist[0] = 0, ways[0] = 1 dist[1] = dist[2] = ∞, ways[1] = ways[2] = 0 Node 0 starts at time 0 with exactly 1 way to be there — standing still. Every other node is unreached.
Step 1 of 4
Solution
function countPaths(n, roads) {
const MOD = 1000000007;
const adj = new Map();
for (let i = 0; i < n; i++) adj.set(i, []);
for (const [u, v, t] of roads) {
adj.get(u).push([v, t]);
adj.get(v).push([u, t]);
}
const dist = new Array(n).fill(Infinity);
const ways = new Array(n).fill(0);
dist[0] = 0;
ways[0] = 1;
const visited = new Set();
while (visited.size < n) {
let current = -1;
let best = Infinity;
for (let i = 0; i < n; i++) {
if (!visited.has(i) && dist[i] < best) {
best = dist[i];
current = i;
}
}
if (current === -1) break;
visited.add(current); // finalized — never revisited
for (const [neighbor, t] of adj.get(current)) {
const candidate = dist[current] + t;
if (candidate < dist[neighbor]) {
dist[neighbor] = candidate;
ways[neighbor] = ways[current];
} else if (candidate === dist[neighbor]) {
ways[neighbor] = (ways[neighbor] + ways[current]) % MOD;
}
}
}
return ways[n - 1] % MOD;
}- Time
- O(n^2 + E)
- Space
- O(n + E)
Test cases
| Input | Expected | Covers |
|---|---|---|
n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]] | 4 | example from the docstring |
n = 3, roads = [[0,1,1],[1,2,1],[0,2,2]] | 2 | a direct edge ties with a two-hop route of the same total time |
n = 1, roads = [] | 1 | source and destination are the same node |
n = 4, roads = [[0,1,1],[1,2,1],[0,2,5],[2,3,1]] | 1 | only one route achieves the shortest time |
n = 3, roads = [[0,1,1],[0,1,1],[1,2,1]] | 2 | two parallel roads between the same intersections count as separate routes |
n = 4, roads = [[0,1,1],[0,2,1],[1,3,1],[2,3,1]] | 2 | two disjoint two-hop routes tie for the shortest time |
n = 5, roads = [[0,1,2],[1,2,2],[2,3,2],[3,4,2]] | 1 | a longer chain with no branching still resolves to a single route |