【每日一题】743. 网络延迟时间
有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间。 times = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
class Solution:
def networkDelayTime(self, times: List], n: int, k: int) -> int:
g = [[] for _ in range(n)]
for x, y, time in times:
g.append((y - 1, time))
dist = * n
dist = 0
q = [(0, k - 1)]
while q:
time, x = heapq.heappop(q)
if dist < time:
# 这里做了优化,如果发现比已有的还要长,实际上就不需要采用这个节点更新图了
continue
for y, time in g:
if (d := dist + time) < dist:
dist = d
heapq.heappush(q, (d, y))
ans = max(dist)
return ans if ans < float('inf') else -1
来源:https://www.cnblogs.com/xxlm/p/18569031
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！
页:
[1]