cells

1976. Number of Ways to Arrive at Destination#

You are in a city that consists of $n$ intersections, numbered from $0$ to $n - 1$. Some intersections are connected by bidirectional roads. It is guaranteed that you can reach any intersection from any other intersection, and that there is at most one road between any two intersections.

You are given an integer $n$ and a 2D integer array $roads$, where $roads[i] = [u_i, v_i, time_i]$ means that there is a road between intersections $u_i$ and $v_i$ that takes $time_i$ minutes to travel. You want to know the number of ways to reach intersection $n - 1$ from intersection $0$ in the minimum possible time.

Return the number of ways to reach the destination with the minimum possible time. Since the answer may be large, return it modulo $10^9 + 7$.

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
Explanation: The minimum time to reach intersection 6 from intersection 0 is 7 minutes.
There are four paths with a minimum time of 7 minutes:
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6

Example 2:

Input: n = 2, roads = [[1,0,10]]
Output: 1
Explanation: There is only one road from intersection 0 to intersection 1, which takes 10 minutes.

Constraints:

• $1 <= n <= 200$
• $n - 1 <= roads.length <= n * (n - 1) / 2$
• $roads[i].length == 3$
• $0 <= u_i, v_i <= n - 1$
• $1 <= time_i <= 10^9$
• $u_i \ne v_i$
• There is at most one road between any two intersections.
• You can reach any intersection from any other intersection.