<div>
You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>), where u<sub>i</sub> is the source node, v<sub>i</sub> is the target node, and w<sub>i</sub> is the time it takes for a signal to travel from source to target.
We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.
Example 1:
<pre>Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2 </pre>
Example 2:
<pre>Input: times = [[1,2,1]], n = 2, k = 1 Output: 1 </pre>
Example 3:
<pre>Input: times = [[1,2,1]], n = 2, k = 2 Output: -1 </pre>
Constraints:
1 <= k <= n <= 1001 <= times.length <= 6000times[i].length == 31 <= u<sub>i</sub>, v<sub>i</sub> <= nu<sub>i</sub> != v<sub>i</sub>0 <= w<sub>i</sub> <= 100- All the pairs
(u<sub>i</sub>, v<sub>i</sub>)are unique. (i.e., no multiple edges.)
</div>
题目大意：
求从某一个点出发的所有能到达的点中的最短时间。若不能都到达返回-1
解题思路：
单源最短路径的最大值，如果有点不能到达返回-1.用BFS+Heap的模板
解题步骤：
N/A
注意事项：
- 用queue
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
# build graph
graph = collections.defaultdict(list)
for e in times:
graph[e[0]].append((e[1], e[2]))
heap = [(0, k)] # weight, node
visited = {k: 0}
while heap:
weight, node = heapq.heappop(heap)
for neighbor, _weight in graph[node]:
if neighbor in visited and visited[neighbor] <= weight + _weight:
continue
heapq.heappush(heap, (weight + _weight, neighbor))
visited[neighbor] = weight + _weight
return max(visited.values()) if len(visited) == n else -1
算法分析：
next时间复杂度为O(V+E)，空间复杂度O(V)
