JZX轻语：简
LeetCode 787 - K站中转内最便宜的航班
发表于2024年05月05日
一开始使用了Dijkstra算法，后面发现不太适用，因为最多K次中转不代表最多K次循环。后面改用了队列+BFS的做法，队列维护节点、从源节点到该节点的路径总开销以及中转站数量，在每次循环中，从队列取出队首，更新节点的最小开销，如果该节点的中转站数量达到k后则不再进行松弛，否则松弛其后继节点并将松弛后的开销加入到队列中。由于一开始没考虑到稠密图的情况，因此可能会出现队列迅速膨胀导致MLE的问题，因此，如果循环中对应节点的开销大于当前的最小开销，则不再继续后面的松弛操作(如果没有负权, 后续的松弛操作是没意义的)。后面想了想，这不就是队列版本的Bellman-Ford算法嘛。
from collections import deque
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
adj_list = [[] for _ in range(n)] # type: List[List[Tuple[int, int]]]
for u, v, cost in flights:
adj_list[u].append((v, cost))
dis = [-1] * n
q = deque([(src, 0, -1)])
while q:
u, dis_cand, cnt = q.popleft()
if dis[u] == -1 or dis[u] > dis_cand:
dis[u] = dis_cand
else:
continue
if cnt == k:
continue
for v, cost in adj_list[u]:
q.append((v, dis_cand + cost, cnt + 1))
return dis[dst]