题目描述

有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。如果没有这样的路线，则输出 -1。

样例

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释: 
城市航班图如上，从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。

示例 2:
输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释: 
城市航班图如上，从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。

提示

• n 范围是 [1, 100]，城市标签从 0 到 n - 1。
• 航班数量范围是 [0, n * (n - 1) / 2]。
• 每个航班的格式 (src, dst, price)。
• 每个航班的价格范围是 [1, 10000]。
• k 范围是 [0, n - 1]。
• 航班没有重复，且不存在环路。

算法1

(堆优化 Dijkstra 求最短路) $O(m \log (nK))$

1. 多个关键字的最短路径问题，dis[i][j] 表示到达了第 i 个点，且到达过 j 个城市的最短距离。
2. 剩下的都是堆优化 Dijkstra 的基本操作了，我们使用优先级队列代替普通队列。

时间复杂度

• 正常堆优化 Dijkstra 的时间复杂度，时间复杂度为 $O(m \log (nk))$。
• 但使用普通优先级队列实现，时间复杂度会达到 $O(m \log m)$，因为队列中每个点不只出现一次。

空间复杂度

• 重建邻接表需要 $O(m)$ 的空间，优先队列需要最多 $O(m)$ 的空间。

C++ 代码

struct Node {
    int no, stops;
    int distance;
    Node(int no_, int stops_, int distance_): no(no_), stops(stops_), distance(distance_) {}
    bool operator > (const Node &other) const {
        return distance > other.distance;
    }
};

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        const int INF = 1000000000;
        vector<vector<pair<int, int>>> graph(n);

        for (const auto &v: flights)
            graph[v[0]].emplace_back(v[1], v[2]);

        K++;
        vector<vector<int>> dis(n, vector<int>(K + 1, INF));
        vector<vector<bool>> vis(n, vector<bool>(K + 1, false));
        priority_queue<Node, vector<Node>, greater<Node>> q;

        q.push(Node(src, 0, 0));
        dis[src][0] = 0;

        while (!q.empty()) {
            Node u = q.top();
            q.pop();

            if (vis[u.no][u.stops])
                continue;

            vis[u.no][u.stops] = true;

            for (const auto &v: graph[u.no])
                if (u.stops + 1 <= K && dis[v.first][u.stops + 1] > dis[u.no][u.stops] + v.second) {
                    dis[v.first][u.stops + 1] = dis[u.no][u.stops] + v.second;
                    q.push(Node(v.first, u.stops + 1, dis[v.first][u.stops + 1]));
                }
        }

        int ans = INF;
        for (int i = 1; i <= K; i++)
            ans = min(ans, dis[dst][i]);

        if (ans == INF)
            ans = -1;

        return ans;
    }
};

算法2

(Bellman-Ford) $O(mK)$

1. 此题也可以看成典型的 Bellman-Ford 求最短路的问题，Bellman-Ford 定义了 dis[i][u] 表示经过了 i 条边后，从源点到点 u 的最短路径。
2. 我们首先枚举 i，然后用每条边更新一次 dis[i] 数组。

时间复杂度

• 对于每一层，都需要 $O(m)$ 的时间更新，故时间复杂度为 $O(mK)$。

空间复杂度

• 重建邻接表需要 $O(m)$ 的空间。

C++ 代码

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        const int INF = 1000000000;
        vector<vector<pair<int, int>>> graph(n);

        for (const auto &v: flights)
            graph[v[0]].emplace_back(v[1], v[2]);

        K++;
        vector<vector<int>> dis(K + 1, vector<int>(n, INF));

        dis[0][src] = 0;

        for (int i = 1; i <= K; i++)
            for (int u = 0; u < n; u++)
                for (const auto &v: graph[u])
                    dis[i][v.first] = min(dis[i][v.first], dis[i - 1][u] + v.second);

        int ans = INF;
        for (int i = 0; i <= K; i++)
            ans = min(ans, dis[i][dst]);

        if (ans == INF)
            ans = -1;

        return ans;
    }
};