#1976 Number of Ways to Arrive at Destination
the problem
In plain words
A city has n intersections (0..n − 1) and two-way roads [u, v, time]. Count how many different routes from 0 to n − 1 take the shortest possible time. Return the count modulo 10⁹ + 7.
in 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]]
out 4
The shortest time is 7, achieved by 4 different routes.
in n = 2, roads = [[1,0,10]]
out 1
- 1 ≤ n ≤ 200
- n − 1 ≤ roads.length ≤ n·(n − 1)/2
- 1 ≤ time ≤ 10⁹
- Connected, at most one road between two intersections
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternDijkstraDP on a DAG
When relaxing u→v: a strictly shorter route resets ways[v] to ways[u]; an equally short route adds ways[u]. Because times are ≥ 1, every predecessor is finalized before v is polled.
solutions
From brute force to optimal
First get all distances. Edges with dist[u] + w == dist[v] form a DAG; count paths in increasing distance order.
- Dijkstra with long distances.
- Sort nodes by dist.
- ways[0] = 1; for u in order, push ways[u] along tight edges.
Dijkstra plus an O(n log n) sort and one pass over edges.
Adjacency list, dist, ways.
class Solution { private static final int MOD = 1_000_000_007; public int countPaths(int n, int[][] roads) { List<List<long[]>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int[] r : roads) { adj.get(r[0]).add(new long[] {r[1], r[2]}); adj.get(r[1]).add(new long[] {r[0], r[2]}); } long[] dist = new long[n]; // long: sums can exceed 2^31 Arrays.fill(dist, Long.MAX_VALUE); dist[0] = 0; PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0])); pq.offer(new long[] {0, 0}); while (!pq.isEmpty()) { long[] top = pq.poll(); int u = (int) top[1]; if (top[0] > dist[u]) continue; for (long[] e : adj.get(u)) { int v = (int) e[0]; if (dist[u] + e[1] < dist[v]) { dist[v] = dist[u] + e[1]; pq.offer(new long[] {dist[v], v}); } } } // Pass 2: edges with dist[u] + w == dist[v] form a DAG. Count paths in distance order. Integer[] order = new Integer[n]; for (int i = 0; i < n; i++) order[i] = i; Arrays.sort(order, (a, b) -> Long.compare(dist[a], dist[b])); long[] ways = new long[n]; ways[0] = 1; for (int u : order) { if (dist[u] == Long.MAX_VALUE) continue; for (long[] e : adj.get(u)) { int v = (int) e[0]; if (dist[u] + e[1] == dist[v]) ways[v] = (ways[v] + ways[u]) % MOD; } } return (int) ways[n - 1]; }}Maintain ways[] next to dist[] during the same Dijkstra.
- dist[0] = 0, ways[0] = 1.
- Relax: nd < dist[v] → dist[v] = nd, ways[v] = ways[u], push. nd == dist[v] → ways[v] += ways[u].
- Return ways[n − 1] mod 10⁹ + 7.
Plain Dijkstra; counting adds O(1) per relaxation.
Adjacency list, heap, dist, ways.
class Solution { private static final int MOD = 1_000_000_007; public int countPaths(int n, int[][] roads) { List<List<long[]>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int[] r : roads) { adj.get(r[0]).add(new long[] {r[1], r[2]}); adj.get(r[1]).add(new long[] {r[0], r[2]}); } long[] dist = new long[n]; long[] ways = new long[n]; Arrays.fill(dist, Long.MAX_VALUE); dist[0] = 0; ways[0] = 1; PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0])); pq.offer(new long[] {0, 0}); while (!pq.isEmpty()) { long[] top = pq.poll(); int u = (int) top[1]; if (top[0] > dist[u]) continue; // ways[u] is final when u is polled for (long[] e : adj.get(u)) { int v = (int) e[0]; long nd = dist[u] + e[1]; if (nd < dist[v]) { // strictly better: reset the count dist[v] = nd; ways[v] = ways[u]; pq.offer(new long[] {nd, v}); } else if (nd == dist[v]) { // another equally short way: add ways[v] = (ways[v] + ways[u]) % MOD; } } } return (int) ways[n - 1]; }}in the room
How to say it in the interview
talk track
- Point out
longdistances: a route can use up to 199 roads × 10⁹ ≈ 2·10¹¹, far pastint. - Explain reset-vs-add on strict vs equal improvements.
traps
intdistances overflow.- Forgetting the modulo on additions.
- Adding ways on ties before u is final — safe here only because weights are positive.
what they ask next
Follow-ups
What if zero-time roads existed?
Then a tie can arrive from a node with the same distance that isn't final yet, and the one-pass count breaks. Use the two-pass version, ordering equal-distance nodes topologically along zero-time edges (a zero-time cycle would make the count infinite).
before you submit
Edge cases to test
- n = 1 → 1 (you are already there).
- Times up to 10⁹ along up to 199 roads overflow
int— uselong. - Many equal routes: a chain of diamonds doubles the count each time, so take the modulo on every addition.
practise next
Similar problems
- #743Network Delay TimeMediumin Shortest Paths
- #2050Parallel Courses IIIHardin Topo Sort
- #62Unique PathsMediumin Dynamic Programming