LeetCode 787 Cheapest Flights Within K Stops

LeetCode

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from<sub>i</sub>, to<sub>i</sub>, price<sub>i</sub>] indicates that there is a flight from city from<sub>i</sub> to city to<sub>i</sub> with cost price<sub>i</sub>.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return-1.

Example 1:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: The graph is shown.
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.

Example 2:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation: The graph is shown.
The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.

Constraints:

1 <= n <= 100 0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3 0 <= from<sub>i</sub>, to<sub>i</sub> < n
from<sub>i</sub> != to<sub>i</sub> 1 <= price<sub>i</sub> <= 10<sup>4</sup>
There will not be any multiple flights between two cities. 0 <= src, dst, k < n
* src != dst

题目大意：

求只允许停k个站情况下，最便宜机票价格

解题思路：

BFS + Heap
这是单源最短路径的典型应用。可以用Dijkstra，机票价格相当于单源最短路径问题中的路径大小。一开始我用BFS，但得到TLE，因为存在循环，导致节点被重复访问(同一路径)。但一个节点的确可以被用不同路径访问。所以引入visited[node] = dis

解题步骤：

N/A

注意事项：

1. node需要被多次访问，所以跟模板不同，visited的检测要放在neighbor循环之外且用node且初始化为空。visited不再是set，它需要记录node离src的距离。一方面用于循环检测，因为如果存在循环，会出现dist >= visited[node]。若该节点的当前距离小于之前的最小距离，此时也要加入到heap，因为贪婪法，虽然此路径费用较高，但它距离更近，当k限制比较小时，此路径可能满足要求。这就是为什么一个节点会被多次访问的原因。
2. 若路径不存在返回-1

Python代码：

def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
	graph = collections.defaultdict(list)
	for pair in flights:
		graph[pair[0]].append((pair[1], pair[2]))
    heap = ([(0, src, 0)]) # price, node_id, distance
	visited = {}
	while heap:
		p, node, dist = heapq.heappop(heap)
		if node == dst and dist <= k + 1:
			return p
		if node in visited and dist >= visited[node]:
			continue
		visited[node] = dist
		for neighbor, _price in graph[node]:
			heapq.heappush(heap, (p + _price, neighbor, dist + 1))
	return -1

算法分析：

时间复杂度为O(VlogV)，空间复杂度O(V)