LeetCode 解題筆記：3620. Network Recovery Pathways

作者：王一哲
日期：2026年7月3日


LeetCode 題目連結：3620. Network Recovery Pathways

解題想法

困難題。題目是有向無環圖，給定數條邊 $edges$ 的資料，代表從節點 $u$ 走到節點 $v$ 的成本 $cost$；$online$ 代表節點 $u$ 是否可以通過；最後要找出是否可以從節點 $0$ 走到節點 $n-1$，回傳所有可以走到終點的路徑最低成本之中的最大值。由於節點數量很多，如果用單純的 BFS 或 DFS 找路徑一定會超時，要對答案二分搜，代入猜測的成本 $mid$，檢查以成本 $mid$ 是否可以符合條件。

Python 程式碼

Runtime: 771 ms, beats 62.50%. Memory: 56.95 MB, beats 81.82%.

class Solution:
    def findMaxPathScore(self, edges: List[List[int]], online: List[bool], k: int) -> int:
        # 1. 用接鄰矩陣存有向圖
        n = len(online)  # n 個節點
        adj = [[] for _ in range(n)]
        max_cost = 0  # 最大成本
        for u, v, c in edges:
            adj[u].append((v, c))
            max_cost = max(max_cost, c)
        
        # 2. 自訂函式，檢查以成本 min_cost 是否可以走到終點
        def check(min_cost):
            dist = [float('inf')] * n  # 走到節點 i 的最低成本
            dist[0] = 0  # 起點成本 0
            pq = [(0, 0)]  # (成本, 節點)
            while pq:
                curr, u = heapq.heappop(pq)
                # 走到終點，curr 是否小於等於 k
                if u == n-1:
                    return curr <= k
                # 如果 curr 大於 dist[u]，無法找到更低成本的路徑
                if curr > dist[u]:
                    continue
                # 檢查 u 的子節點 v
                for v, cost in adj[u]:
                    # 節點 v 不通，找下一個節點
                    if not online[v]:
                        continue
                    # 如果這條邊的成本 cost 小於猜測的最低成本 min_cost
                    if cost < min_cost:
                        continue
                    # 如果找出走到 v 的更低成本路徑，更新 dist[v]，加入 pq
                    nxt = cost + curr
                    if nxt < dist[v]:
                        dist[v] = nxt
                        heapq.heappush(pq, (nxt, v))
            return False
        
        # 3. 對答案二分搜
        low, high, ans = 0, max_cost, -1
        while low <= high:
            mid = (high - low) // 2 + low
            if check(mid):
                # 如果 mid 可以走到終點，設定 ans，再試著用更高的成本測試
                ans = mid
                low = mid + 1
            else:  # 反之，降低成本
                high = mid - 1
        return ans

C++ 程式碼

Runtime: 391 ms, beats 41.89%. Memory: 375.96 MB, beats 38.73%.

class Solution {
public:
    /* 自訂函式，檢查是否可以用 min_cost 走到終點 */
    bool check(long long min_cost, const int n, const vector<vector<pair<int, int>>>& adj, const vector<bool>& online, const long long k) {
        vector<long long> dist (n, LLONG_MAX);
        dist[0] = 0;
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        pq.push({0, 0});
        while(!pq.empty()) {
            long long curr = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            // 走到終點
            if (u == n-1) {
                return curr <= k;
            }
            // curr 大於 dist[u]
            if (curr > dist[u]) continue;
            // 找 u 的子節點
            for(auto it : adj[u]) {
                int v = it.first;
                long long cost = it.second;
                if (!online[v]) continue;
                if (cost < min_cost) continue;
                long long nxt = curr + cost;
                if (nxt < dist[v]) {
                    dist[v] = nxt;
                    pq.push({nxt, v});
                }
            }
        }
        return false;
    }

    int findMaxPathScore(vector<vector<int>>& edges, vector<bool>& online, long long k) {
        /* 1. 用接鄰矩陣存有向圖 */
        int n = (int)online.size(), max_cost = 0;
        vector<vector<pair<int, int>>> adj (n);
        for(auto edge : edges) {
            int u = edge[0], v = edge[1], cost = edge[2];
            adj[u].push_back({v, cost});
            max_cost = max(max_cost, cost);
        }
        /* 2. 對答案二分搜 */
        long long low = 0, high = max_cost, ans = -1;
        while(low <= high) {
            long long mid = (high - low) / 2 + low;
            if (check(mid, n, adj, online, k)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }
};