友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
743. 网络延迟时间
有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点，
wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。
示例 1：
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 输出：2
示例 2：
输入：times = [[1,2,1]], n = 2, k = 1 输出：1
示例 3：
输入：times = [[1,2,1]], n = 2, k = 2 输出：-1
提示：
-
1 <= k <= n <= 100 -
1 <= times.length <= 6000 -
times[i].length == 3 -
1 <= ui, vi <= n -
ui != vi -
0 <= wi <= 100 -
所有
(ui, vi)对都 互不相同（即，不含重复边）
思路分析
没想到竟然是图的最短路径问题。
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-06-04 22:26:14
*/
public int networkDelayTime(int[][] times, int n, int k) {
final int INF = Integer.MAX_VALUE / 2;
int[][] graph = new int[n][n];
for (int[] row : graph) {
Arrays.fill(row, INF);
}
for (int[] t : times) {
graph[t[0] - 1][t[1] - 1] = t[2];
}
int max = 0;
int[] distances = new int[n];
Arrays.fill(distances, INF);
distances[k - 1] = 0;
boolean[] done = new boolean[n];
while (true) {
int x = -1;
for (int i = 0; i < n; i++) {
if (!done[i] && (x < 0 || distances[i] < distances[x])) {
x = i;
}
}
if (x < 0) {
return max; // 最后一次算出的最短路就是最大的
}
if (distances[x] == INF) { // 有节点无法到达
return -1;
}
max = distances[x]; // 求出的最短路会越来越大
done[x] = true; // 最短路长度已确定（无法变得更小）
for (int y = 0; y < n; y++) {
distances[y] = Math.min(distances[y], distances[x] + graph[x][y]);
}
}
}