题目描述
有向带权图，从节点 k 发信号，求传到所有节点的最短用时(取最大的那个)。
edges = 2→1(1), 2→3(1), 3→4(1)
k = 2
输出 = 2
思路解析
dist[源]=0，其他=∞。用最小堆，每次弹出「距离最小且没确定」的点，它的距离就定了，再用它去更新（松弛）邻居的距离。
拓扑排序用普通队列（谁先来谁先出）；带权最短路必须用最小堆，每次取「当前距离最小」的点，不然就算错了。
建图 · 源点 2=0：源点 2 的 dist=0，放进最小堆。边上的数字是权重（用时）。
弹出 2 · 松弛邻居：弹出距离最小的 2（dist=0），敲定。沿着它的边松弛：dist[1]=0+1=1，dist[3]=0+1=1，都入堆。
弹出 1：弹出 1（dist=1），敲定。它没有出边，不用松弛谁。
弹出 3 · 松弛 4：弹出 3（dist=1），敲定。松弛它的邻居 4：dist[4] = dist[3]+1 = 2，然后把 (2, 4) 压入最小堆（heappush）。右侧堆里就出现了 (2,4)。
弹出 4 · 全部确定：弹出 4（dist=2），堆空了，所有点的最短距离都确定了。
答案 = 最大 dist：信号传遍全网的时间 = 所有最短距离里的最大值 = 2。（如果有某个点是 ∞，说明传不到，返回 −1）
和拓扑的 BFS 区别在于：带权图要用最小堆按「距离」取点，而不是按入度。
参考代码（Python）
Python
1g = defaultdict(list)
2for a,b,w in times: g[a].append((b,w)) # 带权邻接表
3dist = {k: 0}; heap = [(0, k)]
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) —— 每条边可能入堆一次
- 空间复杂度：O(V+E) —— 邻接表 + 堆 + dist
套路模板
记住骨架：最小堆按距离取点、能松弛更短就更新并入堆、跳过过期记录。和拓扑 BFS 唯一区别就是「普通队列 → 最小堆」。
Python
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))易错点
- ❌ 用普通队列(FIFO) → ✅ 用最小堆(优先队列)按距离取（带权图必须先处理距离最近的点）
- ❌ 不跳过过期记录 → ✅ if d > dist[u]: continue（同一点可能多次入堆，旧的要跳过）
- ❌ 忘了判断不可达 → ✅ 最后若有点没被访问，返回 -1（有些点信号传不到）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。