3620. Network Recovery Pathways

Description

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] = [u_i, v_i, cost_i] indicates a one‑way communication from node u_i to node v_i with a recovery cost of cost_i.

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:

All intermediate nodes on the path are online.
The total recovery cost of all edges on the path does not exceed k.

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:

The graph has two possible routes from node 0 to node 3:
1. Path 0 → 1 → 3
  - Total cost = 5 + 10 = 15, which exceeds k (15 > 10), so this path is invalid.
2. Path 0 → 2 → 3
  - Total cost = 3 + 4 = 7 <= k, so this path is valid.
  - The minimum edge‐cost along this path is min(3, 4) = 3.
There are no other valid paths. Hence, the maximum among all valid path‐scores is 3.

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:

Node 3 is offline, so any path passing through 3 is invalid.
Consider the remaining routes from 0 to 4:
1. Path 0 → 1 → 4
  - Total cost = 7 + 5 = 12 <= k, so this path is valid.
  - The minimum edge‐cost along this path is min(7, 5) = 5.
2. Path 0 → 2 → 3 → 4
  - Node 3 is offline, so this path is invalid regardless of cost.
3. Path 0 → 2 → 4
  - Total cost = 6 + 6 = 12 <= k, so this path is valid.
  - The minimum edge‐cost along this path is min(6, 6) = 6.
Among the two valid paths, their scores are 5 and 6. Therefore, the answer is 6.

Constraints:

n == online.length
2 <= n <= 5 * 10⁴
0 <= m == edges.length <= min(10⁵, n * (n - 1) / 2)
edges[i] = [u_i, v_i, cost_i]
0 <= u_i, v_i < n
u_i != v_i
0 <= cost_i <= 10⁹
0 <= k <= 5 * 10¹³
online[i] is either true or false, and both online[0] and online[n − 1] are true.
The given graph is a directed acyclic graph.

Solutions

Solution 1: Binary Search + Heap-optimized Dijkstra

The path score is defined as the minimum edge cost along the path. We seek the maximum score among all valid paths.

For a candidate minimum edge weight \(mid\), we only keep edges with cost at least \(mid\), then check whether there exists a path from node \(0\) to node \(n - 1\) with total cost at most \(k\). This reduces to running heap-optimized Dijkstra on the filtered graph.

As \(mid\) increases, fewer edges remain and feasibility becomes harder to satisfy, so we can binary search on \(mid\). We preprocess by removing edges incident to offline nodes, and set \(l\) and \(r\) to the minimum and maximum edge costs. If \(check(l)\) is true, return \(l\); otherwise return \(-1\).

The time complexity is \(O((n + m) \log n \log W)\), and the space complexity is \(O(n + m)\), where \(n\) and \(m\) are the numbers of nodes and edges, and \(W\) is the maximum edge cost.

Python3JavaC++GoTypeScript

class Solution:
    def findMaxPathScore(
        self, edges: List[List[int]], online: List[bool], k: int
    ) -> int:
        def check(mid: int) -> int:
            dist = [inf] * n
            dist[0] = 0
            pq = [(0, 0)]
            while pq:
                d, u = heappop(pq)
                if d > k:
                    return False
                if u == n - 1:
                    return True
                if dist[u] < d:
                    continue
                for v, w in g[u]:
                    if w < mid:
                        continue
                    if dist[u] + w < dist[v]:
                        dist[v] = dist[u] + w
                        heappush(pq, (dist[v], v))
            return False

        n = len(online)
        g = [[] for _ in range(n)]
        l, r = inf, 0
        for (
            u,
            v,
            w,
        ) in edges:
            if not online[u] or not online[v]:
                continue
            g[u].append((v, w))
            l = min(l, w)
            r = max(r, w)

        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l if check(l) else -1

class Solution {
    int n;
    List<int[]>[] g;
    long k;

    boolean check(int mid) {
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE / 4);
        dist[0] = 0;

        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.offer(new long[] {0, 0});

        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            long d = cur[0];
            int u = (int) cur[1];

            if (d > k) return false;
            if (u == n - 1) return true;
            if (dist[u] < d) continue;

            for (int[] e : g[u]) {
                int v = e[0], w = e[1];
                if (w < mid) continue;

                long nd = d + w;
                if (nd < dist[v]) {
                    dist[v] = nd;
                    pq.offer(new long[] {nd, v});
                }
            }
        }

        return false;
    }

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

        int l = Integer.MAX_VALUE;
        int r = 0;

        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (!online[u] || !online[v]) continue;

            g[u].add(new int[] {v, w});
            l = Math.min(l, w);
            r = Math.max(r, w);
        }

        while (l < r) {
            int mid = (l + r + 1) >>> 1;
            if (check(mid))
                l = mid;
            else
                r = mid - 1;
        }

        return check(l) ? l : -1;
    }
}

class Solution {
public:
    int findMaxPathScore(vector<vector<int>>& edges, vector<bool>& online, long long k) {
        int n = online.size();
        vector<vector<pair<int, int>>> g(n);

        int l = INT_MAX, r = 0;

        for (auto& e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (!online[u] || !online[v]) continue;
            g[u].push_back({v, w});
            l = min(l, w);
            r = max(r, w);
        }

        auto check = [&](int mid) -> bool {
            vector<long long> dist(n, LLONG_MAX / 4);
            dist[0] = 0;

            using P = pair<long long, int>;
            priority_queue<P, vector<P>, greater<P>> pq;
            pq.push({0, 0});

            while (!pq.empty()) {
                auto [d, u] = pq.top();
                pq.pop();

                if (d > k) return false;
                if (u == n - 1) return true;
                if (dist[u] < d) continue;

                for (auto& ed : g[u]) {
                    int v = ed.first, w = ed.second;
                    if (w < mid) continue;

                    long long nd = d + w;
                    if (nd < dist[v]) {
                        dist[v] = nd;
                        pq.push({nd, v});
                    }
                }
            }
            return false;
        };

        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid))
                l = mid;
            else
                r = mid - 1;
        }

        return check(l) ? l : -1;
    }
};

type Item struct {
    d int
    u int
}

type H []Item

func (h H) Len() int            { return len(h) }
func (h H) Less(i, j int) bool  { return h[i].d < h[j].d }
func (h H) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *H) Push(x any)         { *h = append(*h, x.(Item)) }
func (h *H) Pop() any           { x := (*h)[len(*h)-1]; *h = (*h)[:len(*h)-1]; return x }

func findMaxPathScore(edges [][]int, online []bool, k int64) int {
    n := len(online)
    g := make([][][]int, n)

    l, r := int(^uint(0)>>1), 0

    for _, e := range edges {
        u, v, w := e[0], e[1], e[2]
        if !online[u] || !online[v] {
            continue
        }
        g[u] = append(g[u], []int{v, w})
        if w < l {
            l = w
        }
        if w > r {
            r = w
        }
    }

    check := func(mid int) bool {
        const INF = int(^uint(0) >> 1)

        dist := make([]int, n)
        for i := range dist {
            dist[i] = INF
        }
        dist[0] = 0

        h := &H{}
        heap.Push(h, Item{0, 0})

        for h.Len() > 0 {
            cur := heap.Pop(h).(Item)
            d, u := cur.d, cur.u

            if int64(d) > k {
                return false
            }
            if u == n-1 {
                return true
            }
            if dist[u] < d {
                continue
            }

            for _, e := range g[u] {
                v, w := e[0], e[1]
                if w < mid {
                    continue
                }
                nd := d + w
                if nd < dist[v] {
                    dist[v] = nd
                    heap.Push(h, Item{nd, v})
                }
            }
        }

        return false
    }

    for l < r {
        mid := (l + r + 1) >> 1
        if check(mid) {
            l = mid
        } else {
            r = mid - 1
        }
    }

    if check(l) {
        return l
    }
    return -1
}

function findMaxPathScore(edges: number[][], online: boolean[], k: number): number {
    const n = online.length;
    const g: [number, number][][] = Array.from({ length: n }, () => []);

    let l = Number.MAX_SAFE_INTEGER;
    let r = 0;

    for (const [u, v, w] of edges) {
        if (!online[u] || !online[v]) continue;
        g[u].push([v, w]);
        l = Math.min(l, w);
        r = Math.max(r, w);
    }

    const check = (mid: number): boolean => {
        const INF = Number.MAX_SAFE_INTEGER / 2;
        const dist = new Array<number>(n).fill(INF);
        dist[0] = 0;

        const pq = new PriorityQueue<[number, number]>((a, b) => a[0] - b[0]);
        pq.enqueue([0, 0]);

        while (!pq.isEmpty()) {
            const [d, u] = pq.dequeue();

            if (d > k) return false;
            if (u === n - 1) return true;
            if (dist[u] < d) continue;

            for (const [v, w] of g[u]) {
                if (w < mid) continue;

                const nd = d + w;
                if (nd < dist[v]) {
                    dist[v] = nd;
                    pq.enqueue([nd, v]);
                }
            }
        }

        return false;
    };

    while (l < r) {
        const mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    return check(l) ? l : -1;
}

3620. Network Recovery Pathways

Description

Solutions

Solution 1: Binary Search + Heap-optimized Dijkstra

Comments