网络延迟：非负有向最短路与最慢接收节点

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• n>0，节点0..n−1，边(u,v,w)非负；允许平行边和零权。
• 延迟为路径边权之和，与q1的路径最高格高度不同；代码返回−1表示至少一个节点不可达。

解题路线

1. Dijkstra的dist[v]是已知最短路上界，最小cost出堆后非负边无法通过更晚点再降低该cost。松弛new=cost+w。
2. heap允许旧条目，出堆cost!=dist[u]则跳过，避免反复用过期距离拓展。不能首次发现就visited，因为后续路径可更短。
3. 广播可并行沿边传播，到达每节点时间为最短路径长度，全部收齐时刻max(dist)；不存在的节点返回−1而不是忽略∞。

手动走一遍

0→1权5、0→2权1、2→1权1：1最终2，广播延迟max(0,2,1)=2，不是首次看到1的5。另有孤立3则−1；只有源节点为0。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from heapq import heappush,heappop


def network_delay(n,edges,start):
    if not 0<=start<n:raise ValueError("invalid source")
    graph=[[] for _ in range(n)]
    for u,v,w in edges:
        if not 0<=u<n or not 0<=v<n or w<0:raise ValueError("valid nonnegative directed edges required")
        graph[u].append((v,w))
    distance=[float('inf')]*n;distance[start]=0;heap=[(0,start)]
    while heap:
        cost,u=heappop(heap)
        if cost!=distance[u]:continue
        for v,w in graph[u]:
            candidate=cost+w
            if candidate<distance[v]:distance[v]=candidate;heappush(heap,(candidate,v))
    result=max(distance)
    return -1 if result==float('inf') else result

复杂度

lazyheap O((V+E)log(V+E))最坏时间、O(V+E)图/堆空间。单位边BFS更简；负权需Bellman-Ford等并检查负环。

易错点与追问

容易失分的边界

• 取全部dist之和不是广播完成时间。
• 原图有向，反向边不可默认存在。

继续深挖

• 返回每节点路径证据如何维护parent？
• 动态边权变化频繁，重算与增量维护有什么正确性风险？