LeetCode 787中等高级图
K 站中转内最便宜的航班 图解题解
这道题到底在问什么
flights[i]=[u,v,w] 表示城市 u 到 v 的票价 w。求从 src 到 dst、最多经过 K 个中转站的最便宜价格；到不了返回 -1。
- 输入
- n=5, src=0, dst=4, k=2, flights=[["0","1",100],["0","2",500],["1","2",100],["1","3",100],["2","4",200],["3","4",100]]
- 输出
- 300
最优解：一步一步想明白
- 3记住这句，下面每一帧都在套它。
- 4最多 2 次中转 = 路径最多 3 条边。先把起点 0 记成 0，其余记 ∞；准备做 3 轮松弛，每轮让路径“多走一条边”。
- 5第 1 轮 · 边 0→1：用上一轮的 dist[0]=0 加票价 100 = 100，比原来的 ∞ 便宜 → 更新 dist[1]=100。
- 6第 1 轮 · 边 0→2：用上一轮的 dist[0]=0 加票价 500 = 500，比原来的 ∞ 便宜 → 更新 dist[2]=500。
- 7第 1 轮 · 边 1→2：上一轮还没到过 1（dist=∞），这条边暂时用不上，跳过。
- 8第 1 轮 · 边 1→3：上一轮还没到过 1（dist=∞），这条边暂时用不上，跳过。
- 9第 1 轮 · 边 2→4：上一轮还没到过 2（dist=∞），这条边暂时用不上，跳过。
- 10第 1 轮 · 边 3→4：上一轮还没到过 3（dist=∞），这条边暂时用不上，跳过。
- 11第 1 轮松弛完毕：此时的 dist 是“最多走 1 条边”能拿到的最便宜价。终点 4 这轮还到不了。
- 12第 2 轮 · 边 0→1：dist[0]=0 加票价 100 = 100，不比现有的 100 便宜 → 不更新。
- 13第 2 轮 · 边 0→2：dist[0]=0 加票价 500 = 500，不比现有的 500 便宜 → 不更新。
- 14第 2 轮 · 边 1→2：用上一轮的 dist[1]=100 加票价 100 = 200，比原来的 500 便宜 → 更新 dist[2]=200。
- 15第 2 轮 · 边 1→3：用上一轮的 dist[1]=100 加票价 100 = 200，比原来的 ∞ 便宜 → 更新 dist[3]=200。
- 16第 2 轮 · 边 2→4：用上一轮的 dist[2]=500 加票价 200 = 700，比原来的 ∞ 便宜 → 更新 dist[4]=700。
- 17第 2 轮 · 边 3→4：上一轮还没到过 3（dist=∞），这条边暂时用不上，跳过。
- 18第 2 轮松弛完毕：此时的 dist 是“最多走 2 条边”能拿到的最便宜价。到终点 4 暂为 700。
- 19第 3 轮 · 边 0→1：dist[0]=0 加票价 100 = 100，不比现有的 100 便宜 → 不更新。
- 20第 3 轮 · 边 0→2：dist[0]=0 加票价 500 = 500，不比现有的 200 便宜 → 不更新。
- 21第 3 轮 · 边 1→2：dist[1]=100 加票价 100 = 200，不比现有的 200 便宜 → 不更新。
- 22第 3 轮 · 边 1→3：dist[1]=100 加票价 100 = 200，不比现有的 200 便宜 → 不更新。
- 23第 3 轮 · 边 2→4：用上一轮的 dist[2]=200 加票价 200 = 400，比原来的 700 便宜 → 更新 dist[4]=400。
- 24第 3 轮 · 边 3→4：用上一轮的 dist[3]=200 加票价 100 = 300，比原来的 400 便宜 → 更新 dist[4]=300。
- 25第 3 轮松弛完毕：此时的 dist 是“最多走 3 条边”能拿到的最便宜价。到终点 4 暂为 300。
- 263 轮全部做完，每轮只让路径多一条边，自然卡住了“最多 2 次中转”。终点 4 的 dist = 300，就是答案。
⚠️ 容易写错的地方
✗ 错：原地松弛不用快照
✓ 对：每轮先复制上一轮 dist 作 snap
不用快照会在一轮里连走多条边，中转数超 K
✗ 错：把轮数写成 K
✓ 对：是 K+1 轮（K 次中转 = K+1 条边）
少一轮会漏掉刚好走满边数的最优解
✗ 错：忘了不可达返回 -1
✓ 对：dist[dst] 仍是 ∞ → -1
K 限制下可能根本到不了终点
完整代码（Python / C++ / Java）
Python
def findCheapestPrice(n, flights, src, dst, k):
INF = float("inf")
dist = [INF] * n
dist[src] = 0
for _ in range(k + 1): # K+1 轮
snap = dist[:] # 上一轮快照
for u, v, w in flights:
if snap[u] + w < dist[v]:
dist[v] = snap[u] + w
return -1 if dist[dst] == INF else dist[dst]C++
#include <vector>
#include <algorithm>
using namespace std;
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k){
const int INF = 1e9;
vector<int> dist(n, INF); dist[src] = 0;
for(int r = 0; r <= k; r++){ // K+1 轮
vector<int> snap = dist; // 上一轮快照
for(auto& f : flights){
int u = f[0], v = f[1], w = f[2];
if(snap[u] != INF && snap[u] + w < dist[v])
dist[v] = snap[u] + w;
}
}
return dist[dst] == INF ? -1 : dist[dst];
}Java
import java.util.*;
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
final int INF = 1000000000;
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[src] = 0;
for (int r = 0; r <= k; r++) { // K+1 轮
int[] snap = dist.clone(); // 上一轮快照
for (int[] f : flights) {
int u = f[0], v = f[1], w = f[2];
if (snap[u] != INF && snap[u] + w < dist[v])
dist[v] = snap[u] + w;
}
}
return dist[dst] == INF ? -1 : dist[dst];
}
}复杂度
时间
O(K · E)
K+1 轮，每轮松弛全部 E 条边
空间
O(n)
dist 数组 + 一份快照
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 K 站中转内最便宜的航班 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么每轮要用上一轮的快照，而不是原地更新？+
原地更新会在同一轮里顺着刚更新的值继续走，等于一轮走了多条边，突破了 K+1 条边的限制，答案会偏小。
能不能用 Dijkstra 做这题？+
不能直接用。Dijkstra 的“取出即确定”会丢掉“边数更多但更便宜”的路；本题有边数上限，按轮松弛的 Bellman-Ford 天然契合。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 K 站中转内最便宜的航班 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。