Number of Ways to Arrive at Destination

Given n intersections numbered 0 through n - 1 and positive-time undirected roads, return the number of routes from 0 to n - 1 whose total travel time is…

Given n intersections numbered 0 through n - 1 and positive-time undirected roads, return the number of routes from 0 to n - 1 whose total travel time is minimum, modulo 1000000007. The graph is connected and simple: there is at most one road between any unordered pair of distinct intersections. Do not modify roads. The empty route from the only vertex to itself counts once when n = 1.

1 ≤ n ≤ 200. n - 1 ≤ roads.length ≤ n × (n - 1) / 2. Each road is [u, v, time], with 0 ≤ u, v < n, u ≠ v, and 1 ≤ time ≤ 1000000000. Distances may reach 199000000000, so use wide arithmetic. Reduce route counts, not distances, modulo 1000000007. A count of zero modulo 1000000007 can represent reachable shortest routes. Visualization alone is limited to 12 vertices, 24 roads and time through 10000; coding retains the full bounds.

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. The direct road and three indirect routes all reach intersection 6 in 7 minutes.

Example 2: input n = 6, roads = [[0,5,8],[0,2,2],[0,1,1],[1,3,3],[1,2,3],[2,5,6],[3,4,2],[4,5,2]]; output 3. Routes 0→5, 0→2→5 and 0→1→3→4→5 each take 8 minutes.

Category: Graphs. Topic: graph. Difficulty: Hard. Patterns: graph-traversal.