LeetCode 787. K 站中转内最便宜的航班

2026-08-02 HGNULB 约 13 分钟

文章信息 7 个分类 6 个标签

分类

题目描述

✅ 787. K 站中转内最便宜的航班

题意分析

给定 $n$ 个城市和一组有向带权边 flights[i] = [from, to, price]，求从 src 飞到 dst 的最低票价总和，但最多只能经过 $k$ 次中转。无法在限制内到达则返回 $-1$。

第一件要做的事是把「中转次数」换算成「边数」。中转指的是在途中落地又起飞的城市，不含起点和终点，所以 $k$ 次中转对应最多 $k+1$ 段航班，也就是路径最多包含 $k+1$ 条边。这个换算一旦搞错，答案就整体偏差一个量级，是本题第一大坑。

第二件事是意识到这个限制破坏了最短路的最优子结构。常规最短路里，「到达某点的最优解」是一个单一的数；但这里到达同一个城市可能有两种方案——便宜但用掉了很多段，或者贵一点但省下了段数。前者未必更优，因为剩余段数不够时它就走不到终点了。所以「到 $u$ 的最小花费」这个状态信息不足，必须把已用边数一并纳入状态。这也直接解释了为什么裸的 Dijkstra 在这题上会出错。

约束给的信号很明确：$1 \le n \le 100$，边数不超过 $n(n-1)/2$ 即约 5000，$0 \le k < n$。$(k+1) \times E$ 最坏约 $100 \times 5000 = 5 \times 10^5$，完全允许「按边数分层、每层扫一遍所有边」的做法。$n$ 只有一百，说明出题人根本不打算考堆优化，考的是你对「边数受限最短路」这一模型的理解。

另外，票价都是正数（$1 \le price \le 10^4$），不存在负权边和负环，所以不需要额外的负环检测；但即便有负权，本解法的分层结构也天然安全——它本来就限制了轮数。

边界方面：$k = 0$ 表示必须直飞；src == dst 时答案为 0；图可能根本不连通，此时要返回 $-1$，所以「不可达」必须用一个能与真实花费区分开的哨兵值表示。

解法：Bellman-Ford（限制边数）

核心思路

先看为什么直接用 Dijkstra 不行。以图 0→1 花费 100、1→2 花费 100、0→2 花费 500，求 0 到 2 且 $k = 0$（必须直飞）为例：Dijkstra 会先确定到 1 的花费 100，再由此确定到 2 的花费 200 并锁定，返回 200；但这条路用了两段航班，超出了限制，正确答案是 500。根本原因就是前面说的——「到达某点的最小花费」不足以刻画状态。

修复方式有两种。一种是给 Dijkstra 扩维，把状态改成「(城市, 已用边数)」，堆里存三元组；另一种更简洁：既然限制的就是边数，那就按边数分层递推。

于是显式写下状态定义：$dist_t[v]$ 表示从 src 出发、恰好使用不超过 $t$ 条边到达城市 $v$ 的最小花费；不可达时为哨兵值 $\text{INF}$。 初始 $dist_0[src] = 0$，其余为 $\text{INF}$（零条边只能停在起点）。

转移是标准的松弛，但关键在于每一层只能引用上一层的值：

$dist_{t+1}[v] = \min\left(dist_t[v],\ \min_{(u,v,w) \in E} \left( dist_t[u] + w \right)\right)$

式中保留 $dist_t[v]$ 这一项，是因为「不超过 $t+1$ 条边」包含了「不超过 $t$ 条边」的所有方案，允许提前抵达、不必把边数用满。实现上这一项由「把上一层的数组整个拷贝为本层初值」自然实现。

必须用两个数组、不能原地更新，这是全题的技术核心。如果在同一轮里直接改 dist 并立刻用改后的值去松弛别的边，一条边刚更新出的结果会在同一轮内被下一条边继续使用，等于一轮走了多条边，边数限制彻底失效，退化成不限边数的最短路。所以每轮开始先拷贝一份，松弛时读旧数组、写新数组，轮末再整体替换。这个「读旧写新」的模式，正是 Bellman-Ford 用于边数受限问题时与朴素写法的唯一区别。

轮数取 $k+1$ 轮（循环变量从 0 到 $k$），因为路径最多 $k+1$ 条边，每轮恰好把可用边数上限加一。

还有一处细节：松弛前要检查 $dist[u] \ne \text{INF}$。若 $u$ 尚不可达却参与计算，$\text{INF} + w$ 会得到一个比 $\text{INF}$ 略大的数，它未必大于其它路径的真实花费，可能被误当成一条合法路径写进 $dist[v]$，进而污染后续所有层。把哨兵取成 $10^9$ 而不是 Integer.MAX_VALUE，则是为了即便忘了这个检查也不至于整数溢出成负数——但检查本身仍然不能省。

最后，$dist[dst]$ 若仍是 $\text{INF}$ 就返回 $-1$，否则返回它。

解题步骤

第一步，建立长度为 $n$ 的 $dist$ 数组，全部填哨兵 $\text{INF}$，然后令 $dist[src] = 0$。 为什么哨兵取 $10^9$ 而不是 Integer.MAX_VALUE：最大可能花费是 $100 \times 10^4 = 10^6$ 量级，$10^9$ 足够大到不会与真实值混淆，同时留出了加法余量，即使意外执行了 $\text{INF} + w$ 也不会溢出成负数。

第二步，循环 $k+1$ 轮（变量从 0 到 $k$）。 为什么是 $k+1$ 而不是 $k$：$k$ 次中转对应 $k+1$ 段航班，每轮松弛让路径可用边数加一。少一轮会漏掉恰好用满边数的最优解，多一轮会允许超限的路径。

第三步，每轮开始先把 $dist$ 完整拷贝到 $newDist$。 为什么要拷贝而不是新建全 $\text{INF}$ 数组：转移式里保留了 $dist_t[v]$ 这一项，含义是「边数没用满也算数」。拷贝正好实现它。若新建全 $\text{INF}$ 数组，状态就变成了「恰好 $t$ 条边」，最终还要在各层之间再取一次最小值，多此一举且容易漏。

第四步，遍历每条边 $(u, v, w)$，若 $dist[u]$ 是 $\text{INF}$ 则跳过。 为什么要跳过：从不可达的点出发松弛是没有意义的，且 $\text{INF} + w$ 这个「伪值」有可能小于其它真实路径的花费而被写入，制造出并不存在的路径。

第五步，执行 $newDist[v] \leftarrow \min(newDist[v],\ dist[u] + w)$。 为什么读的是 $dist[u]$（旧数组）而写的是 $newDist[v]$（新数组）：这是边数限制的实现方式。读新数组会让本轮已更新的结果再次被使用，一轮内串联多条边，限制失效。

第六步，本轮结束后令 $dist \leftarrow newDist$。

第七步，循环结束后，$dist[dst]$ 为 $\text{INF}$ 则返回 $-1$，否则返回 $dist[dst]$。 为什么判 $\text{INF}$ 而不是判「是否被更新过」：哨兵值本身就承担了「不可达」的语义，不需要额外的布尔标记。

以 $n = 3$、flights = [[0,1,100], [1,2,100], [0,2,500]]、src = 0、dst = 2、k = 1 走一遍。$k = 1$ 表示最多中转一次，即最多两段航班。

初始化：$dist = [0,\ \text{INF},\ \text{INF}]$。

第 1 轮（$t = 0$，允许最多 1 条边）：拷贝得 $newDist = [0,\ \text{INF},\ \text{INF}]$。
边 $(0,1,100)$：$dist[0] = 0$ 可达，$newDist[1] = \min(\text{INF},\ 0 + 100) = 100$。
边 $(1,2,100)$：$dist[1] = \text{INF}$（读的是旧数组），跳过。这一步是全题最关键的观察——尽管本轮刚刚把 $newDist[1]$ 更新成了 100，但松弛只看旧数组，所以 0→1→2 这条两段路径不会在只允许一条边的这一轮里被凑出来。
边 $(0,2,500)$：$newDist[2] = \min(\text{INF},\ 0 + 500) = 500$。
本轮结束，$dist = [0,\ 100,\ 500]$。含义是：一条边之内，到 1 花 100（直飞），到 2 花 500（直飞）。

第 2 轮（$t = 1$，允许最多 2 条边）：拷贝得 $newDist = [0,\ 100,\ 500]$。拷贝的作用在这里显现——若本轮找不到更优解，上一轮的 500 会被保留下来，而不是丢失。
边 $(0,1,100)$：$newDist[1] = \min(100,\ 0 + 100) = 100$，无变化。
边 $(1,2,100)$：$dist[1] = 100$ 已可达，$newDist[2] = \min(500,\ 100 + 100) = 200$。这条两段路径终于在允许两条边的这一轮被找到。
边 $(0,2,500)$：$newDist[2] = \min(200,\ 500) = 200$，无变化。
本轮结束，$dist = [0,\ 100,\ 200]$。

两轮跑完，$dist[2] = 200 \ne \text{INF}$，返回 200。对应路线 0 → 1 → 2，两段航班、一次中转，正好卡在 $k = 1$ 的上限内。

把同一组数据的 $k$ 改成 0 再看一眼：只跑第 1 轮，结束时 $dist = [0, 100, 500]$，返回 500，对应必须直飞。这两组结果的对比，恰好说明了「读旧写新」为什么不可省——如果第 1 轮里松弛读的是新数组，边 $(1,2,100)$ 就会用上刚写入的 $newDist[1] = 100$ 算出 200，$k = 0$ 时也返回 200，而正确答案是 500。

代码实现

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], v = e[1], 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) \cdot E)$，其中 $E$ 是航班数。共 $k+1$ 轮，每轮遍历全部边做一次常数时间的松弛，另加一次 $O(n)$ 的数组拷贝。本题 $k < n \le 100$、$E \le n(n-1)/2 \approx 5000$，最坏约 $5 \times 10^5$ 次松弛，毫无压力。注意复杂度与图的稠密程度线性相关，不需要建邻接表——直接遍历边列表反而更简单。

空间复杂度：$O(n)$。只用两个长度为 $n$ 的数组滚动。这里不需要开 $O(nk)$ 的二维表，因为第 $t+1$ 层只依赖第 $t$ 层，把层维滚动掉即可；但必须保留新旧两份，不能压成一份原地更新。

关键点总结

当额外约束破坏最优子结构时，把约束加进状态。「到某点的最小花费」不足以决策，因为边数不同的方案不可比。要么给 Dijkstra 扩一维「已用边数」，要么像本解法一样按边数分层递推。识别出「同一个点的两个方案互不支配」，就是该扩状态的信号。

「读旧写新」是边数受限 Bellman-Ford 的灵魂。朴素 Bellman-Ford 原地更新是允许的（因为它不限边数，早点收敛反而好）；一旦要求「恰好不超过 $t$ 条边」，原地更新就会在一轮内串联多条边。判断标准很简单：本轮的写入会不会被本轮的后续读取用到？会就必须分离新旧。

拷贝上一层作为本层初值，等价于「边数可以不用满」。若改成新建全 $\text{INF}$ 数组，状态语义就变成「恰好 $t$ 条边」，还要在层间额外取最小值。选哪种都行，但要清楚自己定义的是哪一种，并让初始化与之匹配。

哨兵值要同时满足「足够大」和「不溢出」。取 $10^9$ 而非 Integer.MAX_VALUE，是为了给可能发生的加法留余量。更稳妥的做法是像本代码这样在松弛前显式跳过不可达的起点，两道防线一起上。

中转次数与边数差一，务必当场换算。$k$ 次中转 = $k+1$ 段航班 = 循环 $k+1$ 轮。这类「计数口径」的换算，最好在动手前写在纸上，比在调试时反推快得多。

面试视角：面试官最想听的是「为什么不能直接 Dijkstra」，标准答案是给出上面那个 0→1→2 的反例，说明贪心锁定的最优解可能超出边数限制。第二个高频追问是「为什么要拷贝数组」，要能当场演示不拷贝时一轮内串联两条边的过程。如果被问到「有没有别的写法」，可以给出「Dijkstra 扩维成 (城市, 已用边数)」的版本，并说明它在 $k$ 很大而图很稀疏时更快；也可以提一句这题本质上就是一个按层数递推的动态规划，$dist_t[v]$ 就是 DP 状态。能主动指出「$dist[u] == \text{INF}$ 的跳过既是剪枝也是正确性保障」，是很扎实的细节意识。

易错点总结

错误写法：循环只跑 $k$ 轮。以 $n = 3$、flights = [[0,1,100],[1,2,100],[0,2,500]]、src = 0、dst = 2、k = 1 为例，只跑一轮的结果是 $dist[2] = 500$，返回 500，而正确答案是 200。$k$ 次中转允许 $k+1$ 段航班，必须跑 $k+1$ 轮。

错误写法：原地更新 dist，不拷贝新数组。以同一组数据但 $k = 0$ 为例，第一轮中边 $(0,1,100)$ 先把 $dist[1]$ 改成 100，紧接着边 $(1,2,100)$ 读到这个新值算出 200，返回 200，而正确答案是 500（必须直飞）。一轮内串联了两条边，边数限制形同虚设。

错误写法：每轮用全 $\text{INF}$ 的新数组而不是拷贝上一层，且最后不做跨层取最小。以 $n = 3$、flights = [[0,1,100],[0,2,500]]、src = 0、dst = 2、k = 1 为例，第二轮从全 $\text{INF}$ 开始，只有从 1 出发的边能松弛，而 1 没有出边，$dist[2]$ 变回 $\text{INF}$，返回 $-1$，而正确答案是 500。状态语义变成了「恰好两条边」，必须在层间额外取最小值才能补救。

错误写法：松弛前不检查 $dist[u] == \text{INF}$。以任意含不可达中间点的图为例，$\text{INF} + w$ 得到 $10^9 + w$，它虽然比 $\text{INF}$ 大，但若 $newDist[v]$ 此前也是 $\text{INF}$，min 会保留 $\text{INF}$ 而侥幸无事；可一旦哨兵取的是 Integer.MAX_VALUE，加法直接溢出成负数，min 会把这个负值写进去，随后所有依赖 $v$ 的路径全部得出荒谬的负花费。

错误写法：直接套用 Dijkstra，用小根堆按花费取点并在出堆时锁定。以 flights = [[0,1,100],[1,2,100],[0,2,500]]、$k = 0$ 为例，Dijkstra 会先锁定到 1 的花费 100、再锁定到 2 的花费 200，返回 200，而正确答案是 500。同一城市的不同边数方案互不支配，简单锁定必然出错。

错误写法：Dijkstra 扩维时仍用 visited[城市] 做去重。以任意需要「先走贵的短路径再中转」的图为例，某城市第一次以少边数、高花费出堆后就被标记，后续以更低花费但更多边数到达它的状态被丢弃，可能恰好丢掉了通往终点的唯一可行方案。扩维后的访问标记必须按 (城市, 边数) 二元组来记。

错误写法：把中转次数直接当成边数，循环写成 for (t = 0; t < k; t++) 并认为 $k$ 就是边数上限。以 $k = 0$ 为例，循环一次都不执行，$dist$ 保持初值，除非 src == dst 否则一律返回 $-1$，而 $k = 0$ 明明允许直飞。

错误写法：Java 里 int[] newDist = dist;（引用赋值而非 clone()）。以任意输入为例，两个变量指向同一个数组，等同于原地更新，边数限制失效，$k$ 取任何值都会返回不限边数的最短路。Go 侧的对应错误是 newDist := dist（切片共享底层数组）而不是先 make 再 copy。

错误写法：认为票价为正就可以提前在某轮发现 $dist$ 不再变化而退出。以需要恰好用满 $k+1$ 条边的图为例（例如中间几段很便宜、必须多绕几站才划算），提前退出会停在一个尚未最优的层上。朴素 Bellman-Ford 的「无更新即收敛」剪枝在限制边数的版本里不成立，因为我们要的不是收敛值而是恰好第 $k+1$ 层的值。

错误写法：把 src == dst 单独特判成返回 0 之外的值，或忘记初始化 $dist[src] = 0$。以 src = dst = 0 为例，忘记初始化会让 $dist[0]$ 保持 $\text{INF}$，返回 $-1$，而正确答案是 0。起点的零花费是整个递推的唯一种子。

错误写法：用邻接表按点遍历并在同一轮内递归展开。以任意含环的图（如 0→1→2→0）为例，递归展开会沿环无限深入，除非额外传递剩余边数；而按边列表分层松弛天然不受环的影响，因为轮数就是硬上限。本题图中允许存在环，这一点必须防住。

相似题目

题目	难度	考察点
743. 网络延迟时间	中等	无边数限制的标准单源最短路，可直接 Dijkstra 锁定，是本题去掉约束后的原型
778. 水位上升的泳池中游泳	困难	代价函数从求和换成取最大值，Dijkstra 仍适用，考察的是松弛式的可替换性
1631. 最小体力消耗路径	中等	同为瓶颈路，可用 Dijkstra、二分加连通性判定或并查集三种解法对照
1293. 网格中的最短路径	困难	状态同样要扩出一维「剩余可消除障碍数」，与本题扩「已用边数」是同一手法
1129. 颜色交替的最短路径	中等	状态扩出「上一条边的颜色」，边权为 1 可用广搜，训练分层图建模
1334. 阈值距离内邻居最少的城市	中等	点数小的全源最短路，Floyd 三重循环即可，对照单源与多源的选型
505. 迷宫 II	中等	边由「滚到撞墙」的整段滑行构成，重点在建图而非松弛
499. 迷宫 III	困难	距离相同时还要比路径字典序，比较器需要双关键字，是最短路的多目标变体