462. Number of ways to arrive at destination
A city consists of n intersections numbered from 0 to n - 1 with bi-directional roads between some intersections. The inputs are generated such that one can reach any intersection from any other intersection and that there is at most one road between any two intersections.
Given an integer n and a 2D integer array ‘roads’ where roads[i] = [ui, vi, timei] means that there is a road between intersections ui and vi that takes timei minutes to travel. Determine the number of ways to travel from intersection 0 to intersection n - 1 in the shortest amount of time.
Since the answer may be large, return it modulo 109 + 7.
Example 1:
Input: n=7, m=10, 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
Explanation:
The four ways to get there in 7 minutes (which is the shortest calculated time) are:
- 0 6
- 0 4 6
- 0 1 2 5 6
- 0 1 3 5 6
Example 2:
Input: n=6, m=8, 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
Explanation:
The three ways to get there in 8 minutes (which is the shortest calculated time) are:
- 0 5
- 0 2 5
- 0 1 3 4 5
Now Your Turn!
Pick the correct output for the given inputInput: n = 4, m = 4, roads = [[0, 1, 10], [1, 2, 7], [2, 3, 4], [0, 3, 3]]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= n <= 200
- n - 1 <= roads.length <= n * (n - 1) / 2
- roads[i].length == 3
- 0 <= ui, vi <= n - 1
- 1 <= timei <= 109
- ui != vi