787. Cheapest Flights Within K Stops

这道题用bellman-ford就可以了
每次relax的时候存前后结点，最后倒推一遍即可输出路径
O((e+n)logn) time push共e次 pop共n次
改进后的dijkstra，记录所有点k个stop以内的最小费用和（普通的dijkstra是记录所有点的全局最小费用和）

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<int>> graph(n, vector<int>(n, 1e7)); // 用邻接矩阵存图
        for (const auto &f : flights) {
            graph[f[0]][f[1]] = f[2];
        }
        ++K; // 这里K个stop不包括起点和终点，所以要++方便操作，表示K次飞行
        vector<vector<int>> dist(n, vector<int>(K + 1, 1e7)); // cache所有点k次飞行以内的最优解
        auto cmp = [](const vector<int> &lhs, const vector<int> &rhs) {return lhs[2] > rhs[2];};
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> q(cmp); // 用堆记录每个点每次飞行的可能解，这里需要单独存一份开销dist因为把dist传到cmp里不能在堆上即时反应出来
        q.push({src, 0, 0}); // 从src飞到src，0次飞行，开销是0
        // dist[src][0] = 0; // 可写可不写
        while (!q.empty()) {
            auto v = q.top(); q.pop();
            int u = v[0], k = v[1], d = v[2];
            if (u == dst) return d; // 因为堆肯定是最优解（最小费用和）在前，所以第一次碰到dst一定就是最优解
            if (k == K) continue; // 已经达到上限，不propagate了，否则relax时dist[i][k + 1]会outofbound
            for (int i = 0; i < n; ++i) {
                if (dist[i][k + 1] > d + graph[u][i]) { // relax
                    dist[i][k + 1] = d + graph[u][i];
                    q.push({i, k + 1, dist[i][k + 1]});
                }
            }
        }
        return -1;
    }
};

class Solution {
public:
    using tiii = tuple<int, int, int>;
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        ++K;
        vector<vector<pair<int, int>>> g(n);
        for (const auto &f : flights) {
            g[f[0]].emplace_back(f[1], f[2]);
        }
        vector<vector<int>> dist(n, vector<int>(K + 1, INT_MAX));
        priority_queue<tiii, vector<tiii>, greater<tiii>> q;
        q.emplace(0, src, 0);
        dist[src][0] = 0;
        while (!q.empty()) {
            auto [cost, u, k] = q.top(); q.pop();
            if (u == dst) return cost;
            if (k == K) continue;
            for (auto [v, c] : g[u]) {
                if (cost + c < dist[v][k + 1]) {
                    dist[v][k + 1] = cost + c;
                    q.emplace(cost + c, v, k + 1);
                }
            }
        }
        return -1;
    }
};

没做剪枝的版本

class Solution {
public:
    using tiii = tuple<int, int, int>;
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        ++K;
        vector<vector<pair<int, int>>> g(n);
        for (const auto &f : flights) {
            g[f[0]].emplace_back(f[1], f[2]);
        }
        priority_queue<tiii, vector<tiii>, greater<tiii>> q;
        q.emplace(0, src, 0);
        while (!q.empty()) {
            auto [cost, u, k] = q.top(); q.pop();
            if (u == dst) return cost;
            if (k == K) continue;
            for (auto [v, c] : g[u]) {
                q.emplace(cost + c, v, k + 1);
            }
        }
        return -1;
    }
};

bellman-ford变种 O(K*E) time O(VK) space
因为最多只能K个stop，所以relax K次就可以了
每次松弛操作实际上是对相邻节点的访问，第n次松弛操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过 |V|-1 条边，所以可知贝尔曼-福特算法所得为最短路径。
K个stop转换成K+1次飞行，直飞就是1次飞行
f[i][j]表示最多i次飞行从src到达j的最小开销
这里所有的f[i][src] = 0 where 0 <= i <= K + 1

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<int>> d(K + 2, vector<int>(n, 1e7));
        d[0][src] = 0; // 0次飞行哪也去不了，肯定为0
        for (int i = 1; i <= K + 1; ++i) {
            d[i][src] = 0; // 任何次数的飞行都是回到原点
            for (const auto &f : flights) {
                d[i][f[1]] = min(d[i][f[1]], d[i - 1][f[0]] + f[2]); // 进行relax
            }
        }
        return d[K + 1][dst] == 1e7 ? -1 : d[K + 1][dst];
    }
};

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        ++K;
        vector<vector<int>> d(K + 1, vector<int>(n, 1e7));
        d[0][src] = 0;
        for (int i = 1; i <= K; ++i) {
            d[i][src] = 0;
            for (const auto &f : flights) {
                d[i][f[1]] = min(d[i][f[1]], d[i - 1][f[0]] + f[2]);
            }
        }
        return d[K][dst] == 1e7 ? -1 : d[K][dst];
    }
};

滚动数组空间优化以后的bellman-ford变种 O(K*E) time O(V) space

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        ++K;
        vector<vector<int>> d(2, vector<int>(n, 1e7));
        d[0][src] = 0;
        for (int i = 1; i <= K; ++i) {
            d[i & 1][src] = 0;
            for (const auto &f : flights) {
                d[i & 1][f[1]] = min(d[i & 1][f[1]], d[(i - 1) & 1][f[0]] + f[2]);
            }
        }
        return d[K & 1][dst] == 1e7 ? -1 : d[K & 1][dst];
    }
};

加入剪枝

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        ++K;
        vector<vector<int>> d(K + 1, vector<int>(n, 1e7));
        d[0][src] = 0;
        for (int i = 1; i <= K; ++i) {
            d[i][src] = 0;
            bool changed = false;
            for (const auto &f : flights) {
                if (d[i - 1][f[0]] + f[2] < d[i][f[1]]) {
                    d[i][f[1]] = d[i - 1][f[0]] + f[2];
                    changed = true;
                }
            }
            if (!changed) break;
        }
        return d[K][dst] == 1e7 ? -1 : d[K][dst];
    }
};

BFS 如果有圈的话不如dijkstra 比如[[0, 1, 1], [1, 0, 1], [1, 2, 1], [2, 1, 1], [2, 3, 1], [3, 2, 1], [0, 3, 2]] 1stop

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        ++K;
        vector<vector<pair<int, int>>> g(n);
        for (const auto &f : flights) {
            g[f[0]].emplace_back(f[1], f[2]);
        }
        queue<pair<int, int>> q{{{src, 0}}};
        int k = 0, res = INT_MAX;
        while (!q.empty() && k <= K) {
            for (int i = q.size(); i > 0; --i) {
                auto [u, cost] = q.front(); q.pop();
                if (u == dst) {
                    res = min(res, cost);
                }
                for (auto [v, c] : g[u]) {
                    if (cost + c < res) {
                        q.emplace(v, cost + c);
                    }
                }
            }
            ++k;
        }
        return res == INT_MAX ? -1 : res;
    }
};