DSA problem
Number of Ways to Arrive at Destination
You are in a city that consists of n intersections numbered from 0 to n - 1 with bi-directional roads between some intersections. The input roads lists each road as [u, v, time], meaning there is a road between intersections u and v taking time units to traverse in either direction. You start at intersection 0 and want to reach intersection n - 1. Return the number of different shortest paths from 0 to n - 1 modulo 10^9 + 7.
A shortest path here is a path whose total travel time equals dist[n - 1], the minimum possible travel time from 0 to n - 1. Because all edge weights are positive, the standard Dijkstra algorithm computes the shortest distance from the source to every node. The twist is that we must also count paths, not merely find one.
The DP idea grafted onto Dijkstra is a parallel array ways[v] holding the number of distinct shortest paths from 0 to v. Initialize dist[0] = 0, ways[0] = 1, all other dist[v] = ∞, ways[v] = 0. When relaxing an edge (u, v, w) from a popped node u: if dist[u] + w < dist[v], this discovers a strictly shorter path, so set dist[v] = dist[u] + w and copy ways[v] = ways[u] — every shortest path to v now goes through u. If dist[u] + w == dist[v], we found another shortest route into v, so add ways[u] to ways[v] modulo 10^9 + 7.
The correctness of this update relies on Dijkstra's invariant that a node is popped only after its true shortest distance is finalized, so by the time we count paths into v, every shorter route has already been processed. Time complexity is O((n + E) log n) using a binary heap, and space is O(n + E) for the graph, distance, and ways arrays.
Examples
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]]4n = 2, roads = [[1,0,10]]1n = 6, roads = [[0,5,5],[0,1,1],[1,2,1],[2,5,3],[1,3,1],[3,4,1],[4,5,2]]1Constraints
- 1 <= n <= 200
- n - 1 <= roads.length <= n * (n - 1) / 2
- roads[i].length == 3
- 0 <= u_i, v_i <= n - 1
- 1 <= time_i <= 10^9
- u_i != v_i; there is at most one road connecting any two intersections.
- You can reach any intersection from any other intersection.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.