题目来源：
https://leetcode.com/problems/network-delay-time/
自我感觉难度/真实难度：
题意：
分析：
自己的代码：
class Solution:
def networkDelayTime(self, times, N, K):
"""
:type times: List[List[int]]
:type N: int
:type K: int
:rtype: int
"""
K-=1
nodes=collections.defaultdict(list)
for u,v,w in times:
nodes[u-1].append((v-1,w))
dist=[float('inf')]*N
dist[K]=0
done=set()
for _ in range(N):
smallest=min((d,i) for (i,d) in enumerate(dist) if i not in done)[1]
for v,w in nodes[smallest]:
if v not in done and dist[smallest]+w<dist[v]:
dist[v]=dist[smallest]+w
done.add(smallest)
return -1 if float('inf') in dist else max(dist)
代码效率/结果：
Runtime: 152 ms, faster than 83.77% of Python3 online submissions forNetwork Delay Time.
优秀代码：
class Solution:
def networkDelayTime(self, times, N, K):
"""
:type times: List[List[int]]
:type N: int
:type K: int
:rtype: int
"""
h = [(0, K)]
res = 0
reached = set()
d = {}
for u, v, w in times:
if u not in d:
d[u] = []
d[u].append([v, w])
while h:
t, n = heapq.heappop(h)
if n not in reached:
res = t
reached.add(n)
if n in d:
for v, w in d[n]:
if v not in reached:
heapq.heappush(h, [t + w, v])
if len(reached) < N:
return -1
return res
优秀的结题报告，提供了三种超级棒的解答方法：https://blog.****.net/fuxuemingzhu/article/details/82862769
第一次写图的代码，其实草稿纸推一推，发现也不是特别的难，不要畏惧
代码效率/结果：
自己优化后的代码：
反思改进策略：
1.对heapq的模块不熟悉，后面几天着重练习一下堆栈这一块的练习
2.对dijstra算法不熟悉，希望把上面的模块背出来
3.
float('inf')表示正无穷
float('-inf')表示负无穷
4.
dist=[float('inf')]*N
初始化List简单的办法