Description#
You are in a city that consists of n intersections numbered from 0 to n - 1 with bi-directional roads between some intersections. The inputs are generated such 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] = [ui, vi, timei] means that there is a road between intersections ui and vi that takes timei minutes to travel. You want to know in how many ways you can travel from intersection 0 to intersection n - 1 in the shortest amount of time.
Return 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 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 shortest amount of time it takes to go from intersection 0 to intersection 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
Example 2:
Input: n = 2, roads = [[1,0,10]]
Output: 1
Explanation: There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes.
Constraints:
1 <= n <= 200n - 1 <= roads.length <= n * (n - 1) / 2roads[i].length == 30 <= ui, vi <= n - 11 <= timei <= 109ui != vi- There is at most one road connecting any two intersections.
- You can reach any intersection from any other intersection.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution:
def countPaths(self, n: int, roads: List[List[int]]) -> int:
INF = inf
MOD = 10**9 + 7
g = [[INF] * n for _ in range(n)]
for u, v, t in roads:
g[u][v] = t
g[v][u] = t
g[0][0] = 0
dist = [INF] * n
w = [0] * n
dist[0] = 0
w[0] = 1
vis = [False] * n
for _ in range(n):
t = -1
for i in range(n):
if not vis[i] and (t == -1 or dist[i] < dist[t]):
t = i
vis[t] = True
for i in range(n):
if i == t:
continue
ne = dist[t] + g[t][i]
if dist[i] > ne:
dist[i] = ne
w[i] = w[t]
elif dist[i] == ne:
w[i] += w[t]
return w[-1] % MOD
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution {
private static final long INF = Long.MAX_VALUE / 2;
private static final int MOD = (int) 1e9 + 7;
public int countPaths(int n, int[][] roads) {
long[][] g = new long[n][n];
long[] dist = new long[n];
long[] w = new long[n];
boolean[] vis = new boolean[n];
for (int i = 0; i < n; ++i) {
Arrays.fill(g[i], INF);
Arrays.fill(dist, INF);
}
for (int[] r : roads) {
int u = r[0], v = r[1], t = r[2];
g[u][v] = t;
g[v][u] = t;
}
g[0][0] = 0;
dist[0] = 0;
w[0] = 1;
for (int i = 0; i < n; ++i) {
int t = -1;
for (int j = 0; j < n; ++j) {
if (!vis[j] && (t == -1 || dist[j] < dist[t])) {
t = j;
}
}
vis[t] = true;
for (int j = 0; j < n; ++j) {
if (j == t) {
continue;
}
long ne = dist[t] + g[t][j];
if (dist[j] > ne) {
dist[j] = ne;
w[j] = w[t];
} else if (dist[j] == ne) {
w[j] = (w[j] + w[t]) % MOD;
}
}
}
return (int) w[n - 1];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| typedef long long ll;
class Solution {
public:
const ll INF = LLONG_MAX / 2;
const int MOD = 1e9 + 7;
int countPaths(int n, vector<vector<int>>& roads) {
vector<vector<ll>> g(n, vector<ll>(n, INF));
vector<ll> dist(n, INF);
vector<ll> w(n);
vector<bool> vis(n);
for (auto& r : roads) {
int u = r[0], v = r[1], t = r[2];
g[u][v] = t;
g[v][u] = t;
}
g[0][0] = 0;
dist[0] = 0;
w[0] = 1;
for (int i = 0; i < n; ++i) {
int t = -1;
for (int j = 0; j < n; ++j) {
if (!vis[j] && (t == -1 || dist[t] > dist[j])) t = j;
}
vis[t] = true;
for (int j = 0; j < n; ++j) {
if (t == j) continue;
ll ne = dist[t] + g[t][j];
if (dist[j] > ne) {
dist[j] = ne;
w[j] = w[t];
} else if (dist[j] == ne)
w[j] = (w[j] + w[t]) % MOD;
}
}
return w[n - 1];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| func countPaths(n int, roads [][]int) int {
const inf = math.MaxInt64 / 2
const mod = int(1e9) + 7
g := make([][]int, n)
dist := make([]int, n)
w := make([]int, n)
vis := make([]bool, n)
for i := range g {
g[i] = make([]int, n)
dist[i] = inf
for j := range g[i] {
g[i][j] = inf
}
}
for _, r := range roads {
u, v, t := r[0], r[1], r[2]
g[u][v], g[v][u] = t, t
}
g[0][0] = 0
dist[0] = 0
w[0] = 1
for i := 0; i < n; i++ {
t := -1
for j := 0; j < n; j++ {
if !vis[j] && (t == -1 || dist[t] > dist[j]) {
t = j
}
}
vis[t] = true
for j := 0; j < n; j++ {
if j == t {
continue
}
ne := dist[t] + g[t][j]
if dist[j] > ne {
dist[j] = ne
w[j] = w[t]
} else if dist[j] == ne {
w[j] = (w[j] + w[t]) % mod
}
}
}
return w[n-1]
}
|
