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
| class Solution {
private static final int INF = 0x3f3f3f3f;
public int networkDelayTime(int[][] times, int n, int k) {
int[][] g = new int[n][n];
for (int[] e : g) {
Arrays.fill(e, INF);
}
for (int[] t : times) {
int a = t[0] - 1, b = t[1] - 1, w = t[2];
g[a][b] = w;
}
int[] dist = new int[n];
Arrays.fill(dist ,INF);
dist[k - 1] = 0;
boolean[] visited = new boolean[n];
for (int i = 0; i < n; ++i) {
int x = -1;
for (int j = 0; j < n; ++j) {
if (!visited[j] && (x == -1 || dist[x] > dist[j])) {
x = j;
}
}
visited[x] = true;
for (int j = 0; j < n; ++j) {
dist[j] = Math.min(dist[j], dist[x] + g[x][j]);
}
}
int ans = -1;
for (int x : dist) {
ans = Math.max(ans, x);
}
return ans == INF ? -1 : ans;
}
}
|
wechat
