网络延迟时间
Network Delay Time
本机进度仅保存在当前浏览器
题目描述
有 n 个网络节点，标记为 1 到 n。给你一个列表 times，表示信号经过有向边的传递时间 times[i] = (ui, vi, wi)，该信号从节点 ui 经边传到 vi 需要 wi 时间。现在从某个节点 k 发出一个信号，需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。
示例：times = [[2,1,1],[2,3,1],[3,4,1]]，n = 4，k = 2，输出 2。
解题思路
- 单源最短路模板题（边权非负），标准解法是堆优化 Dijkstra，答案为源点到各点最短距离的最大值。
- 维护「已确定最短距离」与「未确定」两个集合：每次从优先队列取出距离最小的节点，它不可能再被更短路径更新，将其定案。
- 松弛：取出节点时若队列中记录的距离大于 dist 表，说明是过期条目，直接跳过；对邻居做 dist 更新并入堆。
- 复杂度 O(E log V)；存在不可达节点时 dist 保持无穷，返回 -1。
参考实现
查看参考实现Python · 建议先自行作答
import heapq
from collections import defaultdict
def networkDelayTime(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {}
heap = [(0, k)] # (距离, 节点)
while heap:
d, node = heapq.heappop(heap)
if node in dist:
continue # 过期条目跳过
dist[node] = d
for nxt, w in graph[node]:
if nxt not in dist:
heapq.heappush(heap, (d + w, nxt))
return max(dist.values()) if len(dist) == n else -1