网络延迟时间
一句话说明
这题本质上就是“有向带权图上的单源最短路”，难点不是建图，而是要先判断它为什么可以直接上 Dijkstra。
先把题目翻译成图论
给定：
n个点times[i] = [u, v, w]
含义就是：
u -> v 有一条权重为 w 的有向边从起点 k 发出信号，问：
所有点都收到信号，最晚要多久？等价于：
- 先求
k到所有点的最短路 - 再取这些最短路里的最大值
为什么这题该用 Dijkstra
因为它满足两个关键条件：
- 单源最短路
- 边权都是非负数
这正是 Dijkstra 的标准应用场景。
解题步骤
- 建邻接表
- 从
k出发跑 Dijkstra - 如果有点不可达，返回
-1 - 否则返回所有最短距离的最大值
Go 代码：标准解法
type Edge struct {
To int
Weight int
}
type State struct {
Node int
Dist int
}
type MinHeap []State
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Dist < h[j].Dist }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any) {
*h = append(*h, x.(State))
}
func (h *MinHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func networkDelayTime(times [][]int, n int, k int) int {
graph := make([][]Edge, n+1)
for _, t := range times {
u, v, w := t[0], t[1], t[2]
graph[u] = append(graph[u], Edge{To: v, Weight: w})
}
const inf = int(1e18)
dist := make([]int, n+1)
for i := 1; i <= n; i++ {
dist[i] = inf
}
dist[k] = 0
h := &MinHeap{{Node: k, Dist: 0}}
heap.Init(h)
for h.Len() > 0 {
cur := heap.Pop(h).(State)
if cur.Dist > dist[cur.Node] {
continue
}
for _, e := range graph[cur.Node] {
candidate := cur.Dist + e.Weight
if candidate >= dist[e.To] {
continue
}
dist[e.To] = candidate
heap.Push(h, State{Node: e.To, Dist: candidate})
}
}
answer := 0
for i := 1; i <= n; i++ {
if dist[i] == inf {
return -1
}
if dist[i] > answer {
answer = dist[i]
}
}
return answer
}为什么答案是最短路里的最大值
因为信号是同时从起点传播出去的。
每个点收到信号的最早时间，就是它的最短距离。
那么“所有点都收到”的时刻，只能取：
最慢的那个点也就是所有最短距离的最大值。
这题最容易卡的地方
1. 建图方向
这是有向图，u -> v 不能同时反向加边。
2. 点编号从 1 开始
很多 Go 模板喜欢 0 下标，这题别混掉。
3. 不可达点
只要有一个点的距离还是无穷大，就说明信号到不了全部节点，答案必须是 -1。
易错点
网络延迟时间最容易错的地方
- 这是有向图，不要误建成无向图。
- Dijkstra 里弹出的堆元素可能过期，要判断后再扩展。
- 最后返回的是“最大最短路”，不是某条单独路径长度。
复杂度
| 指标 | 复杂度 |
|---|---|
| 时间复杂度 | O((V + E)\log V) |
| 空间复杂度 | O(V + E) |