LeetCode 787. K 站中转内最便宜的航班
题目描述
题意分析
航班是带费用的有向边。最多经过
k个中转城市，意味着从起点到终点最多乘坐k + 1段航班；直飞没有中转，但也使用了一条边。除了费用，还要考虑航段数量：到同一城市更便宜的路线可能已经用掉更多航段，不能只按费用把所有路线合并为一个永久确定的状态。可以按允许使用的航段数分层，逐层求最优费用。
解法：Bellman-Ford（限制边数）
核心思路
[!blue]
设第
t轮开始前的dist[v]表示从src出发、最多使用t条边到达城市v的最低费用。初始t = 0，只有起点能以零费用到达，其他位置设为不可达的INF。计算下一层时，先把
dist复制到newDist，保留已经使用不超过t条边的路线。随后遍历每条航班u -> v，若旧层的u可达，就用dist[u] + price尝试更新newDist[v]，表示在一条最多t段的路线后再接上一段航班。这个转移覆盖了所有情况：一条最多
t + 1段的路线，或者已经属于旧层，或者可以拆成到达某个u的前缀和最后一条u -> v。前缀最多使用t段，已由旧层求得最小费用。反过来，每个更新候选也只是在旧路线后增加一段，不会超过新层的航段限制。本轮必须只读
dist、只写newDist。如果直接原地更新，后扫描的航班可能接着使用本轮刚更新的费用，在一轮里连续走过多条边，破坏“一轮只增加一个允许航段”的含义，也会让结果依赖航班的扫描顺序。扫描完全部航班后才用
newDist替换旧层。循环从t = 0到k，共执行k + 1次，最终得到航段上限内的最低费用。目标仍为INF就说明没有合法路线，返回-1。
解题步骤
- 起点零费用，其余不可达。
- 每轮复制旧层。
- 沿全部边，从旧层可达点更新新层。
- 轮末替换，最终返回目标值或负一。
k == 0时仍要执行一轮，允许乘坐一次直飞航班。没有航班或目标无法在限制内到达时，不可达标记会一直保留；从INF出发的边必须跳过。题目最多允许100段、每段费用不超过 $10^4$，10^9足以作为大于所有合法费用的标记。
代码实现
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int INF = 1_000_000_000;
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[src] = 0;
for (int t = 0; t <= k; t++) {
// 保留较少航段的方案，本轮读取旧层、写入新层
int[] newDist = dist.clone();
for (int[] e : flights) {
int u = e[0];
int v = e[1];
int w = e[2];
if (dist[u] == INF) {
continue;
}
// 只从旧层出发增加一条边，不能串联本轮新结果
newDist[v] = Math.min(newDist[v], dist[u] + w);
}
dist = newDist;
}
return dist[dst] == INF ? -1 : dist[dst];
}
}
func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
const INF = int(1e9)
dist := make([]int, n)
for i := range dist {
dist[i] = INF
}
dist[src] = 0
for t := 0; t <= k; t++ {
newDist := make([]int, n)
// 保留较少航段的方案，本轮读取旧层、写入新层
copy(newDist, dist)
for _, e := range flights {
u, v, w := e[0], e[1], e[2]
if dist[u] == INF {
continue
}
// 只从旧层出发增加一条边，不能串联本轮新结果
if dist[u]+w < newDist[v] {
newDist[v] = dist[u] + w
}
}
dist = newDist
}
if dist[dst] == INF {
return -1
}
return dist[dst]
}
复杂度分析
- 时间复杂度：$O((k+1)(n+E))$，每轮含复制与扫描边。
- 空间复杂度：$O(n)$，新旧两层。
关键点总结
[!green]
- 状态是至多若干条边，不是恰好用满。
- 同城市不同航段的方案不能直接用单一锁定状态替代。
易错点总结
[!yellow]
- 原地更新会在一轮串联多条航班。
- 只执行 k 轮，会少允许一段。
- 不保留旧距离，会丢失提前抵达的合法方案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 743. 网络延迟时间 | 中等 | 增加最多中转次数后，同一城市在不同已用步数下不是同一状态，不能只保留一个最低价。 |
| 1928. 规定时间内到达终点的最小花费 | 困难 | 同样在最优路径中增加资源限制，原题限制时间，本题限制经过的边数。 |