2. Linux.do
  3. Leetcode每日一题 —— 3620. 恢复网络路径

Leetcode每日一题 —— 3620. 恢复网络路径

魔法师 2026-07-03 11:52 1


思路


刚做了前两天的题，所以第一想法还是BFS。MLE了，而且感觉同时也TLE了。其实仔细想想会发现，BFS是要遍历所有路径才能找到最终答案的，所以会超时也不奇怪了。


题目要求 最大最小边成本 成本，常见的可以想到二分，而且确实是满足单调性条件的(如果最大分数mid能满足，那么所有<=mid的最大分数都能满足)。

那么解题方法就清晰了，二分可能的最大分数值，每次DFS(因为要求有解而非遍历，所以DFS比BFS一般效率更高)查看是否能够满足。


这次速度快多了，但是卡最后几个案例上，那么就考虑剪枝和记忆化。其实之前是有考虑 TotalCost>k的剪枝，但是依然超时了，这次就新增记忆化搜索，记忆DFS到p点时到终点的总消耗(跟之前剪枝有冲突，就去掉了)，终于过了 ^-^


代码


class Solution {

    private long k;

    private int n;

    private List<int[]>[] path;

    private long[] remainCost;

    public int findMaxPathScore(int[][] edges, boolean[] online, long k) {

        this.k = k;

        n = online.length;

        remainCost = new long[n];

        path = new ArrayList[n];

        int l = Integer.MAX_VALUE, r = 0;

        for (int i = 0; i < n; i++) {

            path[i] = new ArrayList<>();

        }

        for (int[] edge : edges) {

            if (online[edge[0]] && online[edge[1]]) {

                int cost = edge[2];

                l = Math.min(l, cost);

                r = Math.max(r, cost);

                path[edge[0]].add(new int[]{edge[1], cost});

            }

        }

        Arrays.fill(remainCost, -1);

        if (dfs(0, 0) > k) {

            return -1;

        }

        int ans = -1;

        while (l <= r) {

            int mid = (l + r) >> 1;

            Arrays.fill(remainCost, -1);

            if (dfs(mid, 0) <= k) {

                ans = Math.max(ans, mid);

                l = mid + 1;

            } else {

                r = mid - 1;

            }

        }

        return ans;

    }

    private long dfs(int mid, int p) {

        if (p == n - 1) {

            return 0;

        }

        if (remainCost[p] >= 0) {

            return remainCost[p];

        }

        long minRemain = k + 1;

        for (int[] next : path[p]) {

            long cost = next[1];

            if (cost < mid) {

                continue;

            }

            minRemain = Math.min(minRemain, dfs(mid, next[0]) + cost);

        }

        remainCost[p] = minRemain;

        return minRemain;

    }

}
最新回复 (1)
  • SomeBottle 07-03 13:18
    1楼

    看到了内层 + 外层两层约束，max-min 问题，就可以考虑在外层用二分逼近了。


    这题确实也可以这样做，外层直接对结果（最小的边成本）进行二分，而内层则将目前的最小边成本作为约束，限制 Dijkstra 去走小于这个成本的路线。内层的另外一个约束就是 k，找到的最小路径需要 \le k。


    这样一来思路就很清晰了。


    class Solution {
    
public:
    
    int findMaxPathScore(vector<vector<int>>& edges, vector<bool>& online, long long k) {
    
        // 在所有在线节点中执行连通，找最大的最小边成本
    
        // 求总恢复成本依旧可用 Dijkstra，限制在 k 以下
    
        // 而要让最小边成本最大，可以用二分逼近最终结果，限制 Dijkstra 找的边代价只能 >= 结果
    
        int n=online.size();
    
        // 先把 edges 建成图，因为是 DAG，邻接表比较合适
    
        vector<vector<pair<int,int>>> A(n);
    
        for(auto& e:edges){
    
            A[e[0]].emplace_back(e[1],e[2]);
    
        }
    
        // 限制 Dijkstra 找的边代价只能 >= limit，即约束最小边成本
    
        // 在这个基础上找最短路，尽量 <= k
    
        long long maxDist=(long long)(1e9)*50001;
    
        auto djk=[&](int limit) -> bool {
    
            priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
    
            vector<bool> visited(n,false);
    
            vector<long long> dists(n,maxDist);
    
            pq.emplace(0,0);
    
            dists[0]=0;
    
            while(!pq.empty()){
    
                int cDist=pq.top().first;
    
                int cNode=pq.top().second;
    
                pq.pop();
    
                if(visited[cNode]){
    
                    continue;
    
                }
    
                if(cDist>dists[cNode]){
    
                    // 过时节点
    
                    continue;
    
                }
    
                if(cNode==n-1){
    
                    // 确定了到最后节点的最短路径
    
                    return cDist<=k;
    
                }
    
                visited[cNode]=true;
    
                for(auto& adj:A[cNode]){
    
                    if(visited[adj.first]||!online[adj.first]||adj.second<limit){
    
                        // 这个相邻节点访问过 or 不在线 or 边小于 limit，跳过
    
                        continue;
    
                    }
    
                    long long newDist=(long long)cDist+adj.second;
    
                    if(newDist<dists[adj.first]){
    
                        dists[adj.first]=newDist;
    
                        pq.emplace(newDist,adj.first);
    
                    }
    
                }
    
            }
    
            // 不可达
    
            return false;
    
        };
    
        // 二分逼近结果
    
        int l=0,r=(int)(1e9)+1;
    
        int res=-1;
    
        while(l<=r){
    
            int mid=l+((r-l)>>1);
    
            if(djk(mid)){
    
                // 如果以 res 为最小边能找到路径，就移动左边界
    
                res=mid;
    
                l=mid+1;
    
            }else{
    
                // 否则移动右边界
    
                r=mid-1;
    
            }
    
        }
    
        return res;
    
    }
    
};
* 帖子来源Linux.do
附近帖子
返回
飞读
随机推荐