网络延迟时间

最朴素的做法：每一轮在所有还没敲定的点里线性扫一遍，挑出当前 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 区别只有一点：拓扑用普通队列(谁先来谁先出)，带权最短路必须用最小堆按距离取点，否则会先确定一个其实还能更短的点，结果就错了。

边界三连：三种边界先想清。

面试官常追问：四个高频追问，Dijkstra 必背。