【每日一题】743. 网络延迟时间

小圆脸

 
有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间。 times = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
 
 
 
 

1. class Solution:
2.     def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
3.         g = [[] for _ in range(n)]
4.         for x, y, time in times:
5.             g[x - 1].append((y - 1, time))
7.         dist = [float('inf')] * n
8.         dist[k - 1] = 0
9.         q = [(0, k - 1)]
10.         while q:
11.             time, x = heapq.heappop(q)
12.             if dist[x] < time:
13.                 # 这里做了优化,如果发现比已有的还要长,实际上就不需要采用这个节点更新图了
14.                 continue
15.             for y, time in g[x]:
16.                 if (d := dist[x] + time) < dist[y]:
17.                     dist[y] = d
18.                     heapq.heappush(q, (d, y))
20.         ans = max(dist)
21.         return ans if ans < float('inf') else -1

复制代码

 

来源:https://www.cnblogs.com/xxlm/p/18569031
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！