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

◎

本节目标

用分层 Bellman-Ford 限制可使用的边数，求中转次数受限的最低票价。

这是图论综合中“路径还带有步数预算”的母题。k 个中转站最多对应 k + 1 条航班边，不能只按无约束最短路处理。

查看 LeetCode 原题

题意与约束

每个 flights[i] = [from, to, price] 是单向航班。求从 src 到 dst、中转次数不超过 k 的最低价格；若在最多 k + 1 条边内不可达，返回 -1。

直接思路与瓶颈

普通 Dijkstra 只保留“到一个城市的最小价格”，会丢掉已用边数：较便宜但已耗尽预算的状态，未必比略贵但剩余预算更多的状态更好。枚举路径则会组合爆炸。把可用边数作为层次，每层仅从上一层读取距离即可严格限制预算。

图模型与算法推导

令 dist[v] 为最多使用当前轮数条边到 v 的最低价，初始仅 dist[src] = 0。每轮复制 backup = dist，扫描全部航班并只用 backup[from] 松弛 dist[to]。进行 k + 1 轮，正好允许最多 k + 1 条边；不在同轮读取新值，避免一次迭代串用多条航班。

正确性依据

归纳地，开始第 r 轮前 backup 记录至多 r - 1 条边的最佳价格。用其中一条航班松弛后得到的候选恰好使用至多 r 条边，且枚举了最后一条边的所有可能。故 k + 1 轮后 dist[dst] 是预算内最小价格；不可达则保持无穷大并返回 -1。

样例执行过程

flights = [[0,1,100],[1,2,100],[0,2,500]]、src=0、dst=2、k=1。初始 dist=[0,∞,∞]；第 1 层用备份得到 [0,100,500]；第 2 层备份为 [0,100,500]，通过 1 -> 2 得到 200，最终 [0,100,200]。两层对应最多两条边，答案为 200。

代码实现

C++

C++17

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        const long long INF = 1LL << 60;
        vector<long long> dist(n, INF);
        dist[src] = 0;

        for (int stops = 0; stops <= k; stops++) {
            vector<long long> backup = dist;
            for (const auto& flight : flights) {
                const int from = flight[0];
                const int to = flight[1];
                const long long price = flight[2];
                if (backup[from] == INF) {
                    continue;
                }
                dist[to] = min(dist[to], backup[from] + price);
            }
        }

        return dist[dst] == INF ? -1 : static_cast<int>(dist[dst]);
    }
};

Python

Python 3

class Solution:
    def findCheapestPrice(
        self,
        n: int,
        flights: list[list[int]],
        src: int,
        dst: int,
        k: int,
    ) -> int:
        inf = float('inf')
        dist = [inf] * n
        dist[src] = 0

        for _ in range(k + 1):
            backup = dist.copy()
            for source, target, price in flights:
                if backup[source] == inf:
                    continue
                dist[target] = min(dist[target], backup[source] + price)

        return -1 if dist[dst] == inf else int(dist[dst])

复杂度分析

每轮扫描 m 条航班，共 k + 1 轮，时间 O((k + 1)m)；距离数组和备份数组使用 O(n) 额外空间。

边界与易错点

• k 次中转是最多 k + 1 条边，不是 k 条边。
• 每轮必须从 backup 读取，不能原地连锁松弛。
• 不可达的无穷大状态不能参与加法。
• 不引入 SPFA 等额外变体：本题正式解法就是分层松弛。

模式迁移

“最多若干天、操作数或层数”的最短代价问题，可把预算展开为轮次并只读取上一层状态；预算消失时再选择普通最短路模型。