LeetCode 743 Network Delay Time

LeetCode

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:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

Constraints:

1 <= k <= n <= 100 1 <= times.length <= 6000
times[i].length == 3 1 <= u<sub>i</sub>, v<sub>i</sub> <= n
u<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.)

题目大意：

求从某一个点出发的所有能到达的点中的最短时间。若不能都到达返回-1

解题思路：

单源最短路径的最大值，如果有点不能到达返回-1.用BFS+Heap的模板

解题步骤：

N/A

注意事项：

1. 用queue

Python代码：

def 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)