Number of Shortest Paths
Mastery
There are n intersections 0 to n - 1 and two-way roads [a, b, time] with time >= 1. Return the number of different shortest paths (by total time) from 0 to n - 1, modulo 10**9 + 7. If there is no path the answer is 0; for n = 1 the answer is 1.
For n = 4 and roads = [[0, 1, 1], [0, 2, 1], [1, 3, 1], [2, 3, 1]] the answer is 2.
Examples
Example 1
Input:
count_shortest_paths(4, [[0, 1, 1], [0, 2, 1], [1, 3, 1], [2, 3, 1]])
Output:
2
Example 2
Input:
count_shortest_paths(2, [])
Output:
0
Constraints
1 <= n <= 1000000 <= len(roads) <= 2000001 <= time <= 10**4
Theory
Go to TheoryKeywords
dsa-sheetgraphsshortest-paths-and-ordering
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.