Question
Fastest Paths to the Last Village
Imagine a region with n villages, numbered from 0 to n-1, all linked by two-way roads. Every village can be reached from any other, and between any pair of villages there is at most one road.
You’re given a list of these roads, where each entry [u, v, time] tells you how many minutes it takes to travel between village u and village v.
Starting from village 0, you want to reach village n-1 as fast as possible. Your task is to find how many different routes let you reach village n-1 in the minimum travel time.
Input
- The first line contains an integer
n— the number of villages. - The second line contains an integer
m— the number of roads. - The next
mlines each contain 3 space-separated integers — the values of the 2D arrayroads.
Output
Print the number of ways you can arrive at your destination in the shortest amount of time. Since the answer may be large, return it modulo 109 + 7.
Example
Sample Input:
7
10
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
Sample Output:
4
Explanation
The shortest amount of time it takes to go from village 0 to village 6 is 7 minutes.
The four ways to get there in 7 minutes are:
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6
7
10
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
Sample Output:
4
Explanation
The shortest amount of time it takes to go from village 0 to village 6 is 7 minutes.
The four ways to get there in 7 minutes are:
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6