Loading problem...
You are navigating a metropolitan transit network consisting of n stations, labeled from 0 to n - 1. The stations are connected by bidirectional routes, where each route has an associated travel duration. The network is designed such that you can reach any station from any other station, and there is at most one direct route between any pair of stations.
You are provided with an integer n representing the number of stations, and a 2D integer array roads where each element roads[i] = [stationA, stationB, duration] indicates a bidirectional route between stationA and stationB with a travel time of duration minutes.
Your objective is to determine the total count of distinct paths that allow you to travel from station 0 (the origin) to station n - 1 (the final destination) using the minimum possible travel time. Since this count can be astronomically large, return the result modulo 10⁹ + 7.
A path is considered distinct if it traverses a different sequence of stations, even if the total travel time is the same.
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]]4The minimum travel time from station 0 to station 6 is 7 minutes. There are exactly four distinct paths achieving this optimal time: • Direct path: 0 → 6 • Via station 4: 0 → 4 → 6 • Via stations 1, 2, 5: 0 → 1 → 2 → 5 → 6 • Via stations 1, 3, 5: 0 → 1 → 3 → 5 → 6
n = 2
roads = [[1,0,10]]1There is only one possible route connecting station 0 to station 1, and it takes 10 minutes. Hence, there is exactly one path.
n = 4
roads = [[0,1,5],[0,2,5],[1,3,5],[2,3,5]]2The minimum travel time from station 0 to station 3 is 10 minutes. There are two distinct paths achieving this: • 0 → 1 → 3 (duration: 5 + 5 = 10) • 0 → 2 → 3 (duration: 5 + 5 = 10)
Constraints