Count Routes Having Minimum Travel Time

### Problem The connected undirected network has intersections `0` through `n-1`, at most one road per pair, and strictly positive travel times. Return how many routes from intersection 0 to intersection `n-1` attain the minimum possible total travel time. Reduce the count modulo `1000000007`. ```cpp class Solution { public: int countPaths(int n, vector<vector<int>>& roads); }; ``` ### Examples **Example 1:** ```text n = 4, roads = [[0,1,2],[1,3,2],[0,2,1],[2,3,3]] Output: 2 Explanation: Routes 0->1->3 and 0->2->3 both take four minutes. ``` **Example 2:** ```text n = 3, roads = [[0,1,1],[1,2,1],[0,2,5]] Output: 1 Explanation: Only 0->1->2 takes the minimum two minutes. ``` ### Constraints - `1 <= n <= 200`. - `n-1 <= roads.length <= n*(n-1)/2`. - Endpoints are distinct labels in `[0,n-1]`; there are no duplicate roads. - `1 <= time <= 10^9`; the graph is connected. ### Clarifying Questions Different shortest vertex sequences count separately. Every road takes a strictly positive amount of time. ```hint Inspect the structure When a relaxation ties an existing shortest distance, what should happen to its route count? ``` ### Reasoning checkpoints - Count every distinct minimum-time route while excluding longer routes. - Justify the accumulation of route counts and use enough range for travel times before applying the count modulus. ### Optional extensions What breaks in the counting argument if zero-time roads are permitted?