leetcode 743求解

leetcode： 743        Network Delay Time
我写了两个版本，这个是错的：

1. class Solution:
   
2.     def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
   
3.         graph = collections.defaultdict(list)
   
4.         for source, target, time in times:
   
5.             graph[source].append((time, target))
   
6. 
   
7.         q = []
   
8.         heapq.heappush(q, (0, K))
   
9.         arrival = {}
   
10.         arrival[K] = 0
    
11.         while q:
    
12.             time, node = heapq.heappop(q)
    
13.             for t, n in graph[node]:
    
14.                 if n not in arrival:
    
15.                     arrival[n] = time + t
    
16.                     heapq.heappush(q, (time + t, n))
    
17.         res = 0
    
18.         if len(arrival) < N:
    
19.             return -1
    
20.         for i, v in arrival.items():
    
21.             res = max(res, v)
    
22.         return res

复制代码

这个是对的：

1. class Solution:
   
2.     def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
   
3.         graph = collections.defaultdict(list)
   
4.         for source, target, time in times:
   
5.             graph[source].append((time, target))
   
6. 
   
7.         q = []
   
8.         heapq.heappush(q, (0, K))
   
9.         arrival = {}
   
10.         while q:
    
11.             time, node = heapq.heappop(q)
    
12.             if node not in arrival:
    
13.                 arrival[node] = time
    
14.                 for t, n in graph[node]:
    
15.                     heapq.heappush(q, (t+ time, n))
    
16.         res = 0
    
17.         if len(arrival) < N:
    
18.             return -1
    
19.         for i, v in arrival.items():
    
20.             res = max(res, v)
    
21.         return res

复制代码

请各位帮忙指出为哈第一个错了？谢谢!

补充内容 (2019-5-14 14:04):

想明白了，第一个更新节点到达的时间太快了，应该交给priority queue延迟更新才能得到最短路径

想明白了，第一个更新节点到达的时间太快了，应该交给priority queue延迟更新才能得到最短路径。

MST
https://en.wikipedia.org/wiki/Minimum_spanning_tree

其实用不用pq都没关系..

这题用bellman-ford解就行了，就是求到达所有节点的最小可能的值。