带限制的最短路

带限制的最短路

错误示例（Dijkstra）

全局的dist记录着最短距离，但它并未记录是几跳获得的。例如，到达终点的前一跳，从X->dst，我的代码中只限制了到达X最多k+1跳，此时更新了dist[X]，当更新到dst时，利用的dist[X]是经过k跳的X作为跳板，则结果是经过了k+2跳，超出了限制，因此结果必然是错误的。

class Item {
public:
    int node, skip, dis;
    Item(int a, int b, int c):node(a),skip(b),dis(c){}
    bool operator>(const Item& R) const {
        return this->dis > R.dis;
    }
};
class Solution {
public:
    int INF = 0x3f3f3f3f;
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<pair<int, int>>> g(n);
        for (auto& e : flights) g[e[0]].push_back({ e[1], e[2] });
        vector<int> dist(n, INF);
        dist[src] = 0;
        priority_queue<Item, vector<Item>, greater<Item>> pq;
        pq.emplace(src, 0, 0);
        while (!pq.empty()) {
            auto cur = pq.top(); pq.pop();
            int node = cur.node;
            int dis = cur.dis;
            int skip = cur.skip;
            if (skip > k) continue;
            for (auto& e : g[node]) {
                int w_node = e.first;
                int w_weight = e.second;
                if (dist[w_node] > dist[node] + w_weight) {
                    dist[w_node] = dist[node] + w_weight;
                    pq.emplace(w_node, skip + 1, dist[w_node]);
                }
            }
        }
        return dist[dst];
    }
};

再次尝试Dijkstra（完全没必要）

需要扔掉dist，在自定义的结构体中保存dis的值，另外，每次出堆的元素的邻接节点不用判断，全部加入堆。

值得注意的是，由于k的限制存在，堆在这道题完全没有作用，反而会有副作用：

• 假如，题目要求k=0，并且答案经过的这条直接相邻的边权值巨高，则堆会将该方法引向歧途
• 抑或是k的限制，根本不存在答案，需要返回-1，但是由于不加判断，堆会不停进元素，导致死循环

class Item {
public:
    int node, skip, dis;
    Item(int a, int b, int c):node(a),skip(b),dis(c){}
    bool operator>(const Item& R) const {
        return this->dis > R.dis;
    }
};
class Solution {
public:
    int INF = 0x3f3f3f3f;
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<pair<int, int>>> g(n);
        for (auto& e : flights) g[e[0]].push_back({ e[1], e[2] });
        priority_queue<Item, vector<Item>, greater<Item>> pq;
        pq.emplace(src, 0, 0);
        while (!pq.empty()) {
            auto cur = pq.top(); pq.pop();
            int node = cur.node;
            int dis = cur.dis;
            int skip = cur.skip;
            if (node == dst) return dis;
            if (skip > k) continue;
            for (auto& e : g[node]) {
                int w_node = e.first;
                int w_weight = e.second;
                // 不管，全部加入队列
                pq.emplace(w_node, skip + 1, dis + w_weight);
            }
        }
        return -1;
    }
};

bellman(邻接矩阵)

Bellman Ford 核心操作需要遍历所有的边

class Solution {
public:
    int INF = 0x3f3f3f3f;
    int bf(vector<vector<int>>& g, int src, int dst, int k) {
        int n = g.size();
        vector<int> dist(g.size(), INF);
        dist[src] = 0;
        while (k--) {
            vector<int> tmp(dist);
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    dist[j] = min(dist[j], tmp[i] + g[i][j]);
                }
            }
        }
        return dist[dst];
    }
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<int>> g(n, vector<int>(n, INF));
        for (int i = 0; i < n; ++i) g[i][i] = 0;
        for (auto& e : flights) g[e[0]][e[1]] = e[2];
        int ret = bf(g, src, dst, k+1);
        return ret == INF ? -1 : ret;
    }
};

bellman(flights本身就是边)

class Solution {
public:
    int INF = 0x3f3f3f3f;

    int bf(vector<vector<int>>& edg, int src, int dst, int k) {
        int n = edg.size();
        vector<int> dist(edg.size(), INF);
        dist[src] = 0;
        while (k--) {
            vector<int> tmp(dist);
            for (int i = 0; i < n; ++i) {
                for (auto& e : edg) {
                    int x = e[0], y = e[1], w = e[2];
                    dist[y] = min(dist[y], tmp[x] + w);
                }
            }
        }
        return dist[dst];
    }

    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        int ret = bf(flights, src, dst, k+1);
        return ret == INF ? -1 : ret;
    }
};

BFS

class Solution {
public:
    int INF = 0x3f3f3f3f;
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<pair<int, int>>> g(n);
        for (auto& e : flights) g[e[0]].push_back({ e[1], e[2] });
        vector<int> dist(n, INF);
        queue<int> q;
        q.push(src);
        dist[src] = 0;
        while (!q.empty() && k-- >= 0) {
            int sz = q.size();
            vector<int> tmp(dist); // 保留上一时刻的快照
            for (int i = 0; i < sz; ++i) {
                int cur = q.front(); q.pop();
                for (auto& w : g[cur]) {
                    if (dist[w.first] > tmp[cur] + w.second) { // dist!
                        dist[w.first] = tmp[cur] + w.second;
                        q.push(w.first); // 放到if里面（发生更新时才添加元素）
                    }
                }
            }
        }
        return dist[dst] == INF ? -1 : dist[dst];
    }
};