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;
    }
};