leetcode743 Network Delay Time

 1 """
 2 here are N network nodes, labelled 1 to N.
 3 Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.
 4 Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.
 5 Example 1:
 6 Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
 7 Output: 2
 8 """
 9 """
10 此题很经典，是求源点到目标结点的最短路径
11 Dijkstra算法，纯模板题。
12 时间复杂度是O(N^2 + E)，空间复杂度是O(N+E).
13 """
14 class Solution1:
15     def networkDelayTime(self, times, N, K):
16         """
17         :type times: List[List[int]]
18         :type N: int
19         :type K: int
20         :rtype: int
21         """
22         dist = [float(‘inf‘)] * N
23         dist[K - 1] = 0  #K-1是存到距离数组的下标
24         for i in range(N):  #N个结点，遍历N遍更新最短路径
25             for time in times:
26                 u = time[0] - 1 #减1是为了dist的下标一致
27                 v = time[1] - 1
28                 w = time[2]
29                 dist[v] = min(dist[v], dist[u] + w) #更新最短路径
30         return -1 if float(‘inf‘) in dist else max(dist)
31 
32 ss = Solution1()
33 ss.networkDelayTime([[1, 2, 1], [2, 3, 7], [1, 3, 4], [2, 1, 2]], 3, 2)