Cheapest Flights Within K Stops
有 n 座城市，编号从 0 到 n-1，以及一个单程航班列表：flights[i] = [from, to, price] 表示一趟从城市 from 飞往城市 to、票价为 price 的航班。
返回从 src 到 dst 且中途最多停靠 k 次的行程的最低总票价，也就是说，最多乘坐 k+1 趟航班。如果不存在这样的行程，返回 -1。
函数
- ninteger
- 城市数量
- flightsinteger-2d-array
- 单程航班，每个表示为 [from, to, price]
- srcinteger
- 旅程开始的城市
- dstinteger
- 旅程结束的城市
- kinteger
- src 和 dst 之间允许的最多停靠点数
- 返回值integer
- 最多有 k 个中途停靠点的行程的最低价格，或 -1
约束条件
2 ≤ n ≤ 10001 ≤ flights.length ≤ 4500flights[i] = [from, to, price]，其中0 ≤ from, to < n且from ≠ to1 ≤ price ≤ 104- 没有两趟航班的
from和to都相同。 0 ≤ src, dst < n且src ≠ dst0 ≤ k < n
示例
- 输入
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 1
- 输出
- 230
- 解释
- 中转一次允许乘坐两段航班：
0 → 1 → 3的费用是 50 + 180 = 230，而0 → 2 → 3的费用是 200 + 50 = 250。更便宜的0 → 1 → 2 → 3需要中转两次。
- 输入
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 2
- 输出
- 150
- 解释
- 两个停靠点可以乘坐三段航班，所以现在允许
0 → 1 → 2 → 3，费用为 50 + 50 + 50 = 150。
- 输入
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 0
- 输出
- -1
- 解释
- 没有中途停靠的话，这趟行程必须是从 0 到 3 的单程航班，但并没有这样的航班。
进阶
如何返回最便宜行程中的城市以及价格？
提示
逐个打开提示，每个都会多透露一点。
总费用最低的行程可能需要中转太多次，因此仅考虑最短路径还不够。只有结合航班数量，票价才有参考价值。
设
cost[c]表示最多乘坐r次航班到达城市c的最低价格。遍历每一趟航班一次，就能得到最多乘坐r+1次航班时的最低价格。你需要进行这样的k+1轮遍历。每一轮都从上一轮读取价格，并写入一个副本中。如果你原地更新，某个航班就可能基于同一轮中设置的价格，导致一轮中悄悄加入两个航班。
题解
这是一个限制航班次数的最短路径问题。仅在城市上运行 Dijkstra 算法会失败，因为到达某个城市的最便宜路线可能会耗尽剩余行程所需的中转次数。Bellman-Ford 符合这一限制：第 r 轮会找到最多乘坐 r 次航班时的最低票价，因此你需要运行 k+1 轮。
尝试每条最多包含 k+1 个航班的路线
结果正确，但无法在最大的测试中运行完毕
思路
从 src 出发，用一个栈遍历每条路线，栈中记录（城市、价格、已乘坐的航班数）。到达 dst 的路线会记录其价格，然后结束，因为所有价格都为正数。乘坐了 k+1 个航班的路线会被丢弃；其他路线则会从当前城市出发，沿每条航班继续扩展。所有符合条件的行程都会被构建出来，因此记录的最低价格是正确的。
路线数量会按 d 的 k+1 次方增长，其中 d 是每个城市出发的航班数。每个城市有 4 个航班，且 k = 29 时，路线数量为 4^30 ≈ 1.2 × 10^18。
算法
- 按出发城市对航班分组。
- 推入
(src, 0, 0)：城市、当前价格、已乘坐的航班数。 - 弹出一条路线。如果它所在的城市是
dst，并且其价格是目前最优的，就保留这个价格。 - 否则，如果已乘坐的航班少于
k+1个，就为从该城市出发的每个航班推入一条更长的路线。 - 当栈为空时，返回最优价格；如果没有路线到达
dst，则返回 -1。
def findCheapestPrice(n, flights, src, dst, k):
out = [[] for _ in range(n)]
for a, b, price in flights:
out[a].append((b, price))
best = -1
# Each entry is a route in progress: (city, price so far, flights taken).
stack = [(src, 0, 0)]
while stack:
city, cost, used = stack.pop()
if city == dst:
if best == -1 or cost < best:
best = cost
continue
# k stops allow at most k+1 flights.
if used == k + 1:
continue
for nxt, price in out[city]:
stack.append((nxt, cost + price, used + 1))
return bestBellman-Ford 限制为 k+1 轮
思路
令 cost[c] 表示最多乘坐 r 趟航班到达城市 c 的最低价格。当 r = 0 时，只有 src 可以到达，价格为 0。最多乘坐 r 趟航班到达 a，然后乘坐航班 a → b，就能在最多乘坐 r+1 趟航班的情况下到达 b。因此，每一轮都会为每条航班线路提供从 cost[a] + price 到达 b 的价格。经过 k+1 轮后，cost[dst] 就是答案。
每一轮都会读取上一轮的价格，并写入副本，因此本轮设置的价格不能在同一轮中用于另一趟航班。在第一个示例中，k = 1，城市 2 在第 2 轮的价格降到了 100，但已经没有剩余的轮次可以继续飞往城市 3，价格为 150。
每一轮都会读取每条航班线路一次：时间复杂度为 O(k · E)，其中 E 是航班线路数；两个数组的空间复杂度为 O(n)。
算法
- 将
cost[src] = 0，并将其他所有cost设为无穷大。 - 重复
k+1次：将cost复制到next。 - 对于每个航班
[a, b, price]，如果cost[a]是有限值，且cost[a] + price < next[b]，则将next[b] = cost[a] + price。 - 用
next替换cost，如果没有任何变化，则提前停止。 - 返回
cost[dst]；如果它仍是无穷大，则返回 -1。
def findCheapestPrice(n, flights, src, dst, k):
INF = float("inf")
# cost[c]: the cheapest price to reach city c with the flights allowed so far.
cost = [INF] * n
cost[src] = 0
# Each round allows one more flight; k stops means k+1 flights.
for _ in range(k + 1):
# Read last round's prices and write into a copy,
# so one round can never chain two flights.
nxt = cost[:]
changed = False
for a, b, price in flights:
if cost[a] != INF and cost[a] + price < nxt[b]:
nxt[b] = cost[a] + price
changed = True
cost = nxt
if not changed:
break
return -1 if cost[dst] == INF else cost[dst]
易错点和边界情况
- 停止次数按航段数计算。
k次停靠表示k+1个航段和k+1轮。 - 原地更新。按顺序，若每段价格为 1，依次有
0 → 1、1 → 2、2 → 3，另外还有价格为 500 的0 → 3，且k = 0，那么一轮就会串联三个航段，并返回 3，而不是 500。 - 直接在城市上运行 Dijkstra。若每段价格为 1，有
0 → 1和1 → 2，还有价格为 40 的0 → 2、价格为 1 的2 → 3，且k = 1，那么经过两个航段后，城市 2 的距离会确定为 2，并漏掉价格为 41 的0 → 2 → 3。 - 从尚未到达的城市出发。若无穷大是最大的 int，
cost[a] + price会在 32 位整数中溢出为负数。请先检查cost[a]是否为有限值。
常见问题3
“最多 K 次中转的最便宜航班”问题的时间复杂度是多少？
Bellman-Ford 限制为 k+1 轮时，处理 E 条航班需要 O(k · E) 时间，并需要 O(n) 额外空间来存放两个价格数组。如果某一轮没有任何变化，下一轮的价格就会相同，因此你可以提前停止。
为什么 Dijkstra 算法不适用于“最多中转 K 次的最低票价”问题？
Dijkstra 为每个城市保留一个最优价格，不会重新访问已确定的城市。在这里，更贵的路线可能反而有用，因为它乘坐的航班更少。Dijkstra 可以再次用于状态（城市、已乘坐的航班数），这会让状态数量增加到原来的 k+1 倍。
你能用 BFS 解决「最多经过 K 次中转的最便宜航班」问题吗？
是的。第 r 层存放恰好乘坐 r 次航班可到达的城市及其价格。只有当某个城市的新价格低于目前记录的最佳价格时，才把它放到下一层，并在处理完 k+1 层后停止。这样得到的答案与 Bellman-Ford 相同，但只会沿着价格发生变化的城市发出的航班继续搜索。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def findCheapestPrice(n, flights, src, dst, k):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
n = 4 flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]] src = 0 dst = 3 k = 1
预期输出
230