3620. Network Recovery Pathways

  • Graph
  • Binary Search
  • Dynamic Programming
  • Topological Sort
  • Shortest Path
TIME
O((n + m) log m)
SPACE
O(n + m)
problem on leetcode ↗source on github ↗

Intuition

The score of a path is its minimum edge cost, and we want the largest such minimum subject to a total-cost budget k. "Maximize the minimum" with a monotonic feasibility check screams binary search on the answer.

Fix a threshold x. A path can achieve score >= x only if every edge on it has cost >= x. So restrict to edges with cost >= x; a valid path with score >= x exists iff, within that subgraph, the cheapest total-cost path from 0 to n-1 is <= k. As x grows the subgraph shrinks, so feasibility is monotonically non-increasing, binary-searchable.

Approach

  1. Collect the distinct edge costs and sort them; these are the only candidate answers (the score always equals some edge's cost).
  2. Precompute a topological order of the DAG once (Kahn's algorithm).
  3. Feasibility feasible(x): min-total-cost DP over the topo order.
    • dist[0] = 0, everything else INF.
    • Relax each edge u -> v only if cost >= x and both endpoints are online (an offline node can never lie on a valid path): dist[v] = min(dist[v], dist[u] + cost).
    • Feasible iff dist[n-1] <= k.
  4. Binary-search the largest candidate cost x with feasible(x); if even the smallest threshold (all edges) is infeasible, return -1.

Complexity

  • Time: O((n + m) log m), log m feasibility checks, each an O(n + m) topo DP
  • Space: O(n + m), adjacency/topo structures and the dist array

Edge Cases

  • No path within budget → -1
  • Offline intermediate nodes prune edges (endpoints 0 and n-1 always online)
  • k up to 5·10^13 and path sums up to ~n·10^9 → use 64-bit (long); dist sentinel must exceed any real sum
  • Zero-cost edges → threshold 0 is a valid candidate (a path of all-0 edges scores 0)
  • m = 0 → no path unless trivial → -1

Code

from typing import List
from collections import deque


class Solution:
    def findMaxPathScore(self, edges: List[List[int]], online: List[bool], k: int) -> int:
        """
        3620. Network Recovery Pathways
        Time: O((n + m) log m)
        Space: O(n + m)
        """
        # n is the number of nodes; infer from online.
        n = len(online)
        INF = float("inf")

        # Adjacency list and in-degrees for a single topological sort.
        adj = [[] for _ in range(n)]
        indeg = [0] * n
        for u, v, c in edges:
            adj[u].append((v, c))
            indeg[v] += 1

        # Kahn's topological order (computed once, reused across checks).
        topo = []
        dq = deque(i for i in range(n) if indeg[i] == 0)
        deg = indeg[:]
        while dq:
            u = dq.popleft()
            topo.append(u)
            for v, _ in adj[u]:
                deg[v] -= 1
                if deg[v] == 0:
                    dq.append(v)

        def feasible(x: int) -> bool:
            # Min total cost from 0 to n-1 using edges with cost >= x
            # and only online nodes.
            dist = [INF] * n
            dist[0] = 0
            for u in topo:
                du = dist[u]
                if du == INF or not online[u]:
                    continue
                for v, c in adj[u]:
                    if c >= x and online[v] and du + c < dist[v]:
                        dist[v] = du + c
            return dist[n - 1] <= k

        costs = sorted({c for _, _, c in edges})
        if not costs or not feasible(costs[0]):
            return -1

        # Largest candidate cost x with feasible(x).
        lo, hi, ans = 0, len(costs) - 1, -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if feasible(costs[mid]):
                ans = costs[mid]
                lo = mid + 1
            else:
                hi = mid - 1
        return ans