Day77 : 求网络延迟时间

有 N 个网络节点，标记为 1 到 N。

给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。

现在，我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。

示例：

图1

输入：times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2

输出：2

注意:

N 的范围在 [1, 100] 之间。

K 的范围在 [1, N] 之间。

times 的长度在 [1, 6000] 之间。

所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。

力扣: https://leetcode-cn.com/problems/network-delay-time/

class Solution:
def networkDelayTime(self, times, N, K):
# 构建graph
from collections import defaultdict
import heapq
graph = defaultdict(list)
for u,v,w in times:
graph[u].append((v,w))
pq = [(0,K)]
distance = {}
while pq:
d, node = heapq.heappop(pq)
if node in distance: continue
distance[node] = d
for dest, d2 in graph[node]:
if dest not in distance:
heapq.heappush(pq, (d+d2,dest))
return max(distance.values()) if len(distance) == N else -1

def test_networkDelayTime():
s = Solution()
assert s.networkDelayTime([[2,1,1],[2,3,1],[3,4,1]],4,2) == 2