Standard Bar Graphs · Shortest Path Problems O((V + E) log V) · O(V + E)
An emergency network plans dispatch routes between junctions, and the controller wants to know how many distinct fastest corridors exist from base to the incident site — every one of them must be pre-cleared. Whenever two routes tie on total minutes, they count separately; the tally can be huge, so it is reported modulo 10^9 + 7.
Input: An integer n (junctions 0..n-1) and a list roads where [u, v, t] is a bidirectional road taking t minutes.
Output: Return the number of distinct shortest-time routes from 0 to n-1, modulo 10^9 + 7.
1 <= n <= 200n - 1 <= roads.length <= n * (n - 1) / 21 <= t <= 10^9At most one road between any two junctions; the graph is connectedInput: {"n":3,"roads":[[0,1,1],[1,2,1],[0,2,2]]}
Output: 2
The direct 2-minute road and the 1+1 chain tie — two fastest routes.
Input: {"n":2,"roads":[[0,1,100]]}
Output: 1
A single corridor offers exactly one way to arrive.