题目来源：
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代码效率/结果：
自己优化后的代码：
反思改进策略：
1.对heapq的模块不熟悉，后面几天着重练习一下堆栈这一块的练习
2.对dijstra算法不熟悉，希望把上面的模块背出来
3.
float(‘inf‘)表示正无穷
float(‘-inf‘)表示负无穷
4.
dist=[float(‘inf‘)]*N
初始化List简单的办法
743. Network Delay Time
原文地址：https://www.cnblogs.com/captain-dl/p/10293460.html