近似最短路径 (3)

11.3 一些 Leetcode 例题

再来看一些有趣的最短路径变化题吧！

Leetcode 882. Reachable Nodes in Subdivided Graph

https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/
题目叙述：给你一个无向图，现在对於每一条边都把它划分 (subdivide) cnt[i] 次，变成一条新增 cnt[i] 个点的 path。现在请问从 0 出发，有多少个点可以在 maxMoves 步数内走到？
解题想法：(u, v) 这条边被划分以後，其距离从 1 变成了 cnt[i]+1。我们可以先依据这点用 Dijkstra 演算法找出从 0 到原本图上所有点的最短路径长度。接下来，针对每一条边，检查有多少划分後的点在距离内。

检查的时候，可以先分别计算 "左边的点到的了多少个划分点"、然後 "右边的点可以到多少个划分点"，加起来与划分次数取个 min，就不会重复计算也不会少算啦。好题耶！

class Solution {
public:
    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
        vector<vector<pair<int, int>>> adj(n);
        for (auto& e : edges) {
            auto [x, y, c] = tie(e[0], e[1], e[2]);
            adj[x].push_back({y, c});
            adj[y].push_back({x, c});
        }
        vector<int> dist(n, maxMoves + 1);
        vector<bool> visited(n, false);
        set<pair<int, int>> Q;
        Q.insert({0, 0});
        dist[0] = 0;
        
        while (!Q.empty()) {
            auto [d, x] = *Q.begin();
            Q.erase(Q.begin());
            if (visited[x]) continue;
            visited[x] = true;
            for (auto [y, t] : adj[x]) {
                if (!visited[y]) {
                    if (dist[x] + t + 1 < dist[y]) {
                        dist[y] = dist[x] + t + 1;
                        Q.insert({dist[y], y});
                    }
                }
            }
        }
        
        int answer = 0;
        for (int x = 0; x < n; x++) answer += (dist[x] <= maxMoves);
        for (auto& e : edges) {
            auto [x, y, c] = tie(e[0], e[1], e[2]);
            int r1 = max(0, maxMoves - dist[x]);
            int r2 = max(0, maxMoves - dist[y]);
            answer += min(r1 + r2, c);
        }
        return answer;
    }
};

Leetcode 787. Cheapest Flights Within K Stops

https://leetcode.com/problems/cheapest-flights-within-k-stops/
题目叙述：给你一张有向图，每一条有向边表示一个航班。请找出转机次数不超过 k 次、从 src 到 dst 的最便宜路线。
解题想法：我们可以用 Bellman-Ford 的想法，对於边的集合做 k+1 次更新，就可以完成啦！

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        const int INF = 1e9;
        vector<int> dist(n, INF);
        dist[src] = 0;
        while (k-- >= 0) {
            vector<int> nxt = dist;
            for (auto e : flights) {
                auto [x, y, cost] = tie(e[0], e[1], e[2]);
                nxt[y] = min(nxt[y], dist[x] + cost);
            }
            dist.swap(nxt);
        }
        if (dist[dst] != INF) return dist[dst];
        else return -1;
    }
};