题目描述
有向带权图，从节点 k 发信号，求传到所有节点的最短用时，取其中最大的那个；若有点收不到，返回 -1。
思路解析
最朴素的做法：每一轮在所有还没敲定的点里线性扫一遍，挑出当前 dist 最小的那个去确定。点一多，每轮都把全部距离重新比一遍，大量重复比较。
转折：与其每轮线性扫找最小，不如把 (距离, 点) 全丢进最小堆，弹出即取到当前最近的点。它一旦弹出，最短距离就敲定(非负权保证后面不会更短)，再用它去松弛邻居：邻居新距离更短才更新并入堆。能用这招的前提是边权非负。
建图 · 源点 2=0：建带权邻接表。源点 2 的 dist=0，放进最小堆 (0,2)；其余点 dist 视为 ∞。边上的数字是权(用时)。
弹出 2 · 敲定源点：弹出堆顶 (0,2)，它的距离 0 就是 2 的最终最短距离，点 2 敲定(done)。接下来要逐条松弛它指出去的边 2→1 和 2→3。
松弛 1 和 3：松弛 2 的两条出边：dist[1]=0+1=1、dist[3]=0+4=4，都比 ∞ 小，更新并各自入堆 (1,1)、(4,3)。注意 3 暂时是 4，后面会被改短。
弹出 1 · 松弛 3「更短」更新：弹出 (1,1)，点 1 敲定。松弛边 1→3：新距离 1+1=2，比旧的 4 更短！更新 dist[3]=2 并把 (2,3) 入堆。堆里此刻同时有旧的 (4,3) 和新的 (2,3)——同一个点可能多次入堆。
弹出 3 · 松弛 4：弹出更小的 (2,3)，它的距离 2 与 dist[3] 一致，是有效记录，点 3 敲定。松弛边 3→4：dist[4]=2+1=3，入堆 (3,4)。
弹出 4 · 无出边：弹出 (3,4)，点 4 敲定。它没有出边，不松弛任何点。堆里只剩一个 (4,3)——这是点 3 早先的旧记录。
弹出过期记录 (4,3) · 跳过：负例：弹出 (4,3)，但它带的距离 4 大于现在的 dist[3]=2，是被更短路径淘汰掉的过期记录——直接 continue 跳过，不重复松弛。这就是代码里那行 if d 大于 dist[u]: continue 的作用。
全部确定 · 答案=最大 dist：堆空了，四个点全部敲定：dist[2]=0、dist[1]=1、dist[3]=2、dist[4]=3。信号传遍全网的时间 = 所有最短距离里的最大值 = 3。若有某个点仍是 ∞(没进过 dist)，说明传不到，返回 −1。
和拓扑排序的 BFS 区别只有一点：拓扑用普通队列(谁先来谁先出)，带权最短路必须用最小堆按距离取点，否则会先确定一个其实还能更短的点，结果就错了。
参考代码（Python）
1g = defaultdict(list)
2for a, b, w in times: g[a].append((b, w)) # 带权邻接表
3dist = {k: 0}; heap = [(0, k)] # 源点距离 0 入堆
4while heap:
5 d, u = heappop(heap) # 取当前最近的点
6 if d > dist.get(u, INF): continue # 过期旧记录跳过
7 for v, w in g[u]:
8 if d + w < dist.get(v, INF): # 能松弛得更短才更新
9 dist[v] = d + w; heappush(heap, (dist[v], v))
10return max(dist.values()) if len(dist) == n else -1复杂度分析
- 时间复杂度：O(E·logV) —— 每条边最多触发一次入堆，堆操作 logV；E 条边共 E·logV
- 空间复杂度：O(V+E) —— 邻接表 O(V+E) + 堆和 dist O(V)
套路模板
记住骨架：最小堆按距离取点、能松弛更短才更新并入堆、跳过过期记录。和拓扑 BFS 唯一区别就是「普通队列 → 最小堆」。
1# 非负权单源最短路都套这个骨架
2dist = {src: 0}; heap = [(0, src)]
3while heap:
4 d, u = heappop(heap) # 取当前最近的点
5 if d > dist.get(u, INF): continue # 过期记录跳过
6 for v, w in g[u]:
7 if d + w < dist.get(v, INF): # 能松弛得更短
8 dist[v] = d + w; heappush(heap, (dist[v], v))易错点
- 错误写法：只要 d + w 不为 ∞ 就更新 dist[v] → 正确写法：if d + w < dist.get(v, INF) 才更新（松弛必须「更短才更新」；无脑覆盖会把已有的更短距离改回大值，答案全错）
- 错误写法：用普通队列(FIFO)按入队顺序取点 → 正确写法：用最小堆(优先队列)按距离取点（带权图必须先敲定当前最近的点，先进先出会先确定一个其实还能更短的点）
- 错误写法：不跳过过期记录，重复松弛 → 正确写法：if d > dist.get(u, INF): continue（同一点可能多次入堆，旧的更大记录要跳过，否则做无用功甚至覆盖）
- 错误写法：直接 return max(dist.values()) → 正确写法：先判 len(dist)==n，有点没进 dist 返回 -1（有些点信号传不到，dist 里压根没有它，必须判不可达）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。