← All problems

3620. Network Recovery Pathways

HardOpen on LeetCodeProblem statement

Problem Statement

3620. Network Recovery Pathways

Hard

You are given a directed acyclic graph of n nodes numbered from 0 to n − 1. This is represented by a 2D array edges of length m, where edges[i] = [ui, vi, costi] indicates a one‑way communication from node ui to node vi with a recovery cost of costi.

Some nodes may be offline. You are given a boolean array online where online[i] = true means node i is online. Nodes 0 and n − 1 are always online.

A path from 0 to n − 1 is valid if:

For each valid path, define its score as the minimum edge‑cost along that path.

Return the maximum path score (i.e., the largest minimum-edge cost) among all valid paths. If no valid path exists, return -1.

 

Example 1:

Input: edges = [[0,1,5],[1,3,10],[0,2,3],[2,3,4]], online = [true,true,true,true], k = 10

Output: 3

Explanation:

Example 2:

Input: edges = [[0,1,7],[1,4,5],[0,2,6],[2,3,6],[3,4,2],[2,4,6]], online = [true,true,true,false,true], k = 12

Output: 6

Explanation:

 

Constraints:

Java

Source file
class Solution {

    public int findMaxPathScore(int[][] edges, boolean[] online, long k) {
        int n = online.length;
        List<int[]>[] g = new ArrayList[n];
        int[] deg = new int[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }

        int l = Integer.MAX_VALUE,
            r = 0;
        for (int[] edge : edges) {
            int u = edge[0],
                v = edge[1],
                w = edge[2];
            if (!online[u] || !online[v]) {
                continue;
            }
            g[u].add(new int[] { v, w });
            deg[v]++;
            l = Math.min(l, w);
            r = Math.max(r, w);
        }

        // Delete unreachable nodes
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i < n; i++) {
            if (deg[i] == 0) {
                q.offer(i);
            }
        }
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int[] edge : g[u]) {
                int v = edge[0];
                if (--deg[v] == 0 && v != 0) {
                    q.offer(v);
                }
            }
        }

        if (!check(l, k, g, deg, n)) {
            return -1;
        }

        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid, k, g, deg, n)) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return r;
    }

    private boolean check(int mid, long k, List<int[]>[] g, int[] deg, int n) {
        long[] dp = new long[n];
        Arrays.fill(dp, Long.MAX_VALUE / 2);
        int[] cdeg = deg.clone();
        dp[0] = 0;

        Queue<Integer> q = new LinkedList<>();
        q.offer(0);

        while (!q.isEmpty()) {
            int u = q.poll();
            if (u == n - 1) {
                return dp[u] <= k;
            }

            for (int[] edge : g[u]) {
                int v = edge[0],
                    w = edge[1];
                if (w >= mid) {
                    dp[v] = Math.min(dp[v], dp[u] + w);
                }
                if (--cdeg[v] == 0) {
                    q.offer(v);
                }
            }
        }
        return false;
    }
}