LeetCode 787 Cheapest Flights Within K Stops

LeetCode

<div>

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:

<pre>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. </pre>

Example 2:

<pre>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. </pre>

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

</div>

题目大意：

求只允许停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)

算法II解题思路(推荐)：

算法一比较难想，如果我们用BFS+Heap模板，我们用visited记录单点最贵price。但是此题由于有边数限制的最值问题，所以类似于DP，将限制条件引入作为参数或state。
visited[(node, distance)]=total_price
两处剪枝：

1. 价格超过visited
2. 路径长度超过k
   其实法一也是用了两个剪枝条件，因为price低肯定是先出堆，所以只要比较某点最短路径visited即可，后出堆的点如果路径更长(价格肯定更高了)，肯定可以剪枝。

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 = {(src, 0): 0} # (node, distance): price
	while heap:
		p, node, dist = heapq.heappop(heap)
		if node == dst:
			return p
		if dist == k + 1:
			continue
		for neighbor, _price in graph[node]:
			if (neighbor, dist + 1) in visited and visited[(neighbor, dist + 1)] <= p + _price:
				continue
			heapq.heappush(heap, (p + _price, neighbor, dist + 1))
			visited[(neighbor, dist + 1)] = p + _price
	return -1