Napman's Notes

Network Recovery Pathways

Properties1
tagsreview/leetcode

3 min read

3620. Network Recovery Pathways

Difficulty: Hard | Date: 2026-07-03

Patterns: Binary Search | Graphs Data Structures: Array

Problem

Given a directed weighted graph of n nodes (0 to n-1), a list of booleans online for each node, and a budget k, find the maximum path score from node 0 to node n-1. A path is valid if all nodes are online and total edge weight <= k. The path score is the minimum edge weight along the path.

My Approach

Started with BFS/Dijkstra intuition - track total weight and minimum edge weight at each node. Realized you’d need to keep too many incomparable states at each node. Then didn’t immediately see the binary search angle - needed a nudge toward the “maximize the minimum” pattern.

Once I saw binary search on T (the edge weight threshold), the inner check became simple: run Dijkstra on only edges with weight >= T to find the minimum total weight path. If that weight <= k, T is achievable.

Initial bugs: forgot to filter edges by T in the condition function, used append(v, weight) instead of append((v, weight)), set n = len(edges) instead of n = len(online), flipped the binary search direction, and added reverse edges making the graph undirected when it’s actually directed.

Key Insight

“Maximize the minimum” = binary search on the answer. The signal is the monotonic property: if T=7 works (a valid path exists using only edges >= 7 with total weight <= k), then T=6, T=5, etc. also work - you can always use the same path since those edges are still >= the lower threshold. This monotonicity is what makes binary search valid. Binary search on T, filter to edges with weight >= T, run Dijkstra to find the minimum total weight path. If min path weight <= k, T is achievable - search higher. The directed edge constraint is easy to miss - don’t add reverse edges.

Solution

from collections import defaultdict
from heapq import heappush, heappop
 
def solution(n, edges, online, k):
    def dijkstra(graph, start):
        dist = [float('inf')] * n
        dist[start] = 0
        heap = [(0, start)]
        while heap:
            cost, u = heappop(heap)
            if cost > dist[u]:
                continue
            for v, weight in graph[u]:
                if dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight
                    heappush(heap, (dist[v], v))
        return dist
 
    def condition(T):
        graph = defaultdict(list)
        for u, v, weight in edges:
            if weight >= T and online[u] and online[v]:
                graph[u].append((v, weight))  # directed - no reverse edge
        dist = dijkstra(graph, 0)
        return dist[n - 1] <= k
 
    l = min(w for _, _, w in edges)
    r = max(w for _, _, w in edges)
    ans = -1
    while l <= r:
        mid = (l + r) // 2
        if condition(mid):
            ans = mid
            l = mid + 1
        else:
            r = mid - 1
    return ans

Complexity

  • Time: O(log(W) * (V + E) log V) - log(W) binary search iterations, each running Dijkstra
  • Space: O(V + E) - graph and dist array

Prerequisites

Review Log

  • 2026-07-11 [Good] - fuzzy: binary search bounds (was thinking 0 to k, not min/max edge weight), Dijkstra is O((V+E) log V) not O(V+E); clicked: filtering edges >= mid removes need to track min edge weight during traversal
  • 2026-07-25 [Good] - fuzzy: binary search direction (move right when condition true), Dijkstra intuition (need min total weight path), Dijkstra is O((V+E) log V) not O(V+E); clicked: filter edges >= T, run Dijkstra to check total cost <= k

Graph View