787. Cheapest Flights Within K Stops

題目網址：https://leetcode.cn/problems/cheapest-flights-within-k-stops/

題意：有 n 個城市通過一些航班連接。給一整數 array flights, 其中 flights[i] = [from_i, to_i, price_i] , 表示該航班都從城市 from_i 開始, 以價格 price_i 抵達 to_i。

給定所有的城市和航班, 以及起點 src 和終點 dst, 找出一條最多經過 k 站中轉的 path, 使得從 src 到 dst 的價格最便宜, 並返回該價格。 如果不存在這樣的 path, 則返回 -1。

Solution 1：

想法：利用 Dijkstra 演算法

• 建立 adjacent lit
• 建立 min heap
• 執行 BFS

typedef pair<int, int> pii; // {weight, next}
typedef tuple<int, int, int> t3i; // {cost, cur, times}

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<pii>> adj(n); // adjacent list
        for (const auto& f : flights) {
            adj[f[0]].emplace_back(pii{f[2], f[1]});
        }

        vector<vector<bool>> calculated(n, vector<bool>(k + 1, false));
        priority_queue<t3i, vector<t3i>, greater<>> pq; // max heap
        pq.emplace(t3i{0, src, 0});

        while (!pq.empty()) {
            for (int i = pq.size(); i > 0; --i) {
                const auto [cost, cur, times] = pq.top();
                pq.pop();

                // 抵達終點, 返回 cost
                if (cur == dst) {
                    return cost;
                }

                // 若不為終點, 且已中轉 k + 1 次, 代表 cur 不可能到終點, 故跳過
                if (times == k + 1) {
                    continue;
                }

                // 若中轉 times 次抵達 cur 的 cost 已計算過, 則跳過
                // 因為中轉 times 次抵達 cur 的 cost 為最佳解, 其延伸出去的邊已加到 pq 中
                if (calculated[cur][times]) {
                    continue;
                }

                // 若 cur 還未計算中轉 times 次的 cost
                calculated[cur][times] = true;

                // 將 cur 所延伸出去的邊加入到 pq 中
                for (const auto& [price, next] : adj[cur]) {
                    pq.emplace(t3i{cost + price, next, times + 1});
                }
            }
        }
        return -1;
    }
};

• time：$O(E \cdot log(E))$ ➔ Dijkstra 的時間複雜度, 因為 pq 中最多有 E 條邊, 每次 push / pop 元素需花 $O(log(E))$
• space：$O(V + E)$ ➔ 因為 adj 為 $O(V + E)$, V 是因為要記錄所有點, E 是因為會記錄所有邊

Solution 2：

想法：「不超過 k 個中繼點」等價於「不超過 k + 1 個航班 (邊)」, 利用 Bellman-Ford 演算法, 用 dist[i][j] 表示飛不超過 i 次航班抵達 j 的最少價格

• path = 0 ➔ 2 中間沒有任何中繼點
• path = 0 ➔ 1 ➔ 2 中間有 1 個中繼點 1

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<int>> dist(k + 2, vector<int>(n, INT_MAX));
        dist[0][src] = 0; // 飛 0 次, 在起點的價格為 0

        for (int i = 1; i <= k + 1; ++i) {
            dist[i][src] = 0; // 每次 dist[i][src] 都初始化為 0, 因為在起點的價格為 0

            for (const auto& f : flights) {
                const int u = f[0], v = f[1], price = f[2];

                // 若 u 目前無法直接抵達, 則跳過
                // 若不處理, 下面 dis[i - 1][u] + price 會 overflow
                if (dist[i - 1][u] == INT_MAX) {
                    continue;
                }

                // u 可直接抵達, 則更新 u -> v 的 shortest path
                dist[i][v] = min(dist[i][v], dist[i - 1][u] + price);
            }
        }
        return (dist[k + 1][dst] == INT_MAX) ? -1 : dist[k + 1][dst];
    }
};

• time：$O(k \cdot E)$ ➔ for loop
• space：$O(k \cdot n)$ ➔ dist

Solution 3：

想法：改進 Solution 2, 因為 dist[i][v] 只會使用到 dist[i - 1][u], 因此不需要保存每一次的狀態, 只需保存上一次的狀態即可。用 prev 紀錄不超過 i - 1 個中繼點的狀態, 而 dist 紀錄不超過 i 個中繼點的狀態

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int> dist(n, INT_MAX);
        dist[src] = 0;

        for (int i = 0; i <= k; ++i) {
            vector<int> prev = dist; // prev 初始化為不超過 (i - 1) 個中繼點的狀態

            for (const auto& f : flights) {
                const int u = f[0], v = f[1], price = f[2];

                // 若 u 無法直接抵達, 則跳過
                // 若不處理, 下面 prev[u] + price 會 overflow
                if (prev[u] == INT_MAX) {
                    continue;
                }

                // u 可直接抵達, 則更新 u -> v 的 shortest path
                dist[v] = min(dist[v], prev[u] + price);
            }
        }
        // 此時的 dist 為不超過 k 個中繼點的狀態
        return (dist[dst] == INT_MAX) ? -1 : dist[dst];
    }
};

• time：$O(k \cdot E)$ ➔ for loop
• space：$O(n)$ ➔ prev, dist