hardGraphsPure DSA~40 min
Number of Distinct Fastest Routes
Across a weighted road network between intersection 0 and intersection n-1, count how many distinct routes achieve the minimum travel time. Two routes differ if their edge sequences differ.
Problem
You are given n intersections (0..n-1) and a list of bidirectional roads where roads[i] = [u, v, time]. Return the number of ways to travel from intersection 0 to intersection n-1 in the shortest possible time, modulo 1e9+7.
Input
An integer n and roads as [u, v, time] triples.
Output
An integer: the count of shortest paths, modulo 1e9+7.
Constraints
- 1 <= n <= 200
- n - 1 <= roads.length <= n*(n-1)/2
- 1 <= time <= 10^9; exactly one road per pair; the graph is connected.
Examples
Example 1
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
4
Four different routes all reach node 6 in the minimum time of 7.
Example 2
Input
n = 2, roads = [[1,0,10]]
Output
1
The only route takes time 10.