3620. Network Recovery Pathways
Problem Description
You are given a directed acyclic graph with n nodes labeled 0 through n - 1. The 2D array edges has m entries, where edges[i] = [uᵢ, vᵢ, costᵢ] describes a one-way link from node uᵢ to node vᵢ that takes costᵢ units to recover.
Some nodes are down. The boolean array online records which ones are working: online[i] = true means node i is up. Nodes 0 and n - 1 are guaranteed to be up.
A route from node 0 to node n - 1 counts as valid when both of the following hold:
- Every node strictly between the two endpoints is online.
- The recovery costs of the edges along the route add up to at most
k.
Each valid route earns a score equal to the cheapest edge that appears on it. Return the largest score over all valid routes. If no valid route exists, return -1.
Example 1: Given edges = [[0,1,5],[1,3,10],[0,2,3],[2,3,4]], online = [true,true,true,true], and k = 10, the output is 3. Two routes lead from node 0 to node 3. The route 0 → 1 → 3 sums to 5 + 10 = 15, which is over the budget of 10, so it is invalid. The route 0 → 2 → 3 sums to 3 + 4 = 7, which fits the budget, and its cheapest edge is min(3, 4) = 3. That is the only valid route, so the answer is 3.
Example 2: Given 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], and k = 12, the output is 6. Node 3 is down, so the route 0 → 2 → 3 → 4 is ruled out no matter what it costs. The route 0 → 1 → 4 totals 7 + 5 = 12 with cheapest edge 5; the route 0 → 2 → 4 totals 6 + 6 = 12 with cheapest edge 6. The better of the two scores is 6.
Constraints:
n == online.lengthand2 <= n <= 5 * 10⁴0 <= m == edges.length <= min(10⁵, n * (n - 1) / 2)edges[i] = [uᵢ, vᵢ, costᵢ]with0 <= uᵢ, vᵢ < nanduᵢ != vᵢ0 <= costᵢ <= 10⁹0 <= k <= 5 * 10¹³online[0]andonline[n - 1]are bothtrue- The graph contains no directed cycles.
How We Pick the Algorithm
Why Binary Search + Dijkstra?
This problem maps to Binary Search + Dijkstra through a short path in the full flowchart.
Binary search on the score (the cheapest edge a route may use); each guess is verified by running Dijkstra over edges costing at least the guess and checking that some 0 → n-1 route stays within the budget k.
Open in FlowchartIntuition
Every route is judged by two different numbers at once: its total cost, which must stay within the budget k, and its cheapest edge, which we want to make as large as possible. A single traversal struggles to optimize both together. A route whose edges are all expensive scores well but may spend too much in total, while the cheapest route overall may cross one very cheap edge and score poorly. The two objectives pull in opposite directions.
The way out is to turn the optimization into a yes/no question. Instead of asking "what is the best score?", fix a guess x and ask: does some valid route use only edges costing at least x? This question has a useful monotone structure. If a route qualifies for x, the very same route qualifies for every smaller guess, because each of its edges is still expensive enough. So as x grows, the answer flips from yes to no exactly once, and the largest x that still gets a yes is the score we want. That is the setting for a binary search on the answer. Since the score of any route equals one of its edge costs, only the distinct edge costs need to be tried as guesses.
For a fixed guess x, the check becomes an ordinary shortest-path problem. Discard every edge cheaper than x and every edge that touches an offline node, then compute the cheapest total from node 0 to node n - 1 in what remains. The guess is feasible exactly when that cheapest total is at most k — if even the cheapest qualifying route blows the budget, every other qualifying route does too. All costs are non-negative, so Dijkstra with a min-heap answers this directly. The input happens to be acyclic, so a relaxation in topological order would work as well; Dijkstra does not need the ordering.
Offline nodes need no special machinery during the search: a valid route may only pass through online intermediate nodes, and the two endpoints are always online, so keeping an edge only when both of its endpoints are online removes every forbidden route and nothing else.
Solution Approach
Solution: Binary Search on the Answer + Dijkstra
The solution has three parts: filter the graph once, define a feasibility test, and binary search over the candidate answers.
Filtering the graph
Build an adjacency list that keeps an edge [u, v, cost] only when online[u] and online[v] are both true. Because nodes 0 and n - 1 are always online, a route in the filtered graph is exactly a route whose intermediate nodes are all online. While filtering, collect the costs of the kept edges; after sorting and removing duplicates they form the candidate answers. If no edge survives, no route can exist and the answer is -1.
The feasibility test: Dijkstra with a cost floor
feasible(x) asks whether some route from 0 to n - 1 uses only edges costing at least x and has total cost at most k. Run Dijkstra from node 0, but while relaxing, skip any edge with cost < x, and only accept a new distance d + cost when it does not exceed k. Because every pushed distance already respects the budget, the test can stop with a yes as soon as node n - 1 is popped from the heap. If the heap drains first, the target is unreachable within budget and the test answers no.
Distances must be stored in 64-bit integers: a route can traverse up to 10⁵ edges of cost up to 10⁹, and k itself reaches 5 * 10¹³, both far beyond a 32-bit range.
Binary search over distinct edge costs
Let costs be the sorted distinct usable edge costs. Standard binary search finds the largest element for which feasible answers yes:
lo, hi = 0, len(costs) - 1 ans = -1 while lo <= hi: mid = (lo + hi) // 2 if feasible(costs[mid]): ans = costs[mid] # record and try a larger guess lo = mid + 1 else: hi = mid - 1 # too strict; try a smaller guess return ans
If no guess is feasible — including the smallest edge cost, which permits every usable edge — then no valid route exists at all and ans stays -1.
Complexity Analysis:
- Time complexity:
O((n + m) · log n · log m). Sorting the distinct costs takesO(m log m). The binary search performsO(log m)feasibility tests, and each test is one Dijkstra run costingO((n + m) log n). - Space complexity:
O(n + m)for the adjacency list, the distance array, and the heap.
Example Walkthrough
Let's trace Example 2: 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.
Phase 1: Filter the graph
Node 3 is offline, so every edge touching it is dropped.
| Edge | Online check | Kept? |
|---|---|---|
0 → 1 (cost 7) | both online | yes |
1 → 4 (cost 5) | both online | yes |
0 → 2 (cost 6) | both online | yes |
2 → 3 (cost 6) | node 3 offline | no |
3 → 4 (cost 2) | node 3 offline | no |
2 → 4 (cost 6) | both online | yes |
The distinct usable costs, sorted, are costs = [5, 6, 7].
Phase 2: Binary search
Start with lo = 0, hi = 2, ans = -1.
Iteration 1 — mid = 1, guess x = 6.
Edges costing at least 6: 0 → 1 (7), 0 → 2 (6), 2 → 4 (6). The edge 1 → 4 (5) is off limits. Dijkstra from node 0:
| Pop | Relaxations |
|---|---|
(0, node 0) | node 1 gets 7, node 2 gets 6 (both <= 12) |
(6, node 2) | node 4 gets 6 + 6 = 12 <= 12 |
(7, node 1) | its only edge 1 → 4 costs 5 < 6, skipped |
(12, node 4) | target reached within budget — feasible |
Record ans = 6 and move lo = 2.
Iteration 2 — mid = 2, guess x = 7.
Only 0 → 1 (7) survives the floor. Dijkstra reaches node 1 at distance 7, but the edge 1 → 4 costs 5 < 7 and is skipped. The heap drains without touching node 4 — infeasible. Move hi = 1.
Now lo = 2 > hi = 1, so the search stops.
Result
The answer is ans = 6, matching the expected output: the route 0 → 2 → 4 spends exactly 12 and never uses an edge cheaper than 6.
Solution Implementation
1import heapq
2from typing import List
3
4
5class Solution:
6 def findMaxPathScore(self, edges: List[List[int]], online: List[bool], k: int) -> int:
7 n = len(online)
8
9 # Build the adjacency list, keeping only edges whose endpoints are
10 # both online. Nodes 0 and n-1 are guaranteed online, so a route in
11 # the filtered graph is exactly a route with online intermediates.
12 graph = [[] for _ in range(n)]
13 cost_set = set()
14 for u, v, cost in edges:
15 if online[u] and online[v]:
16 graph[u].append((v, cost))
17 cost_set.add(cost)
18
19 # No usable edge means node n-1 cannot be reached at all.
20 if not cost_set:
21 return -1
22
23 # The score of any route equals one of its edge costs, so the
24 # sorted distinct usable costs are the candidate answers.
25 costs = sorted(cost_set)
26
27 def feasible(threshold: int) -> bool:
28 # Dijkstra restricted to edges with cost >= threshold.
29 # Returns True if some 0 -> n-1 route has total cost <= k.
30 dist = [float("inf")] * n
31 dist[0] = 0
32 heap = [(0, 0)] # (distance so far, node)
33 while heap:
34 d, u = heapq.heappop(heap)
35 # Skip stale entries whose recorded distance is outdated.
36 if d > dist[u]:
37 continue
38 # Every pushed distance already respects the budget, so
39 # reaching the target means a valid route exists.
40 if u == n - 1:
41 return True
42 for v, cost in graph[u]:
43 # Edges cheaper than the current guess are forbidden.
44 if cost < threshold:
45 continue
46 nd = d + cost
47 # Discard routes that already exceed the budget k.
48 if nd <= k and nd < dist[v]:
49 dist[v] = nd
50 heapq.heappush(heap, (nd, v))
51 return dist[n - 1] <= k
52
53 # Binary search the largest edge cost that still admits a valid route.
54 ans = -1
55 lo, hi = 0, len(costs) - 1
56 while lo <= hi:
57 mid = (lo + hi) // 2
58 if feasible(costs[mid]):
59 ans = costs[mid] # record and try a larger guess
60 lo = mid + 1
61 else:
62 hi = mid - 1 # too strict; try a smaller guess
63 return ans
641class Solution {
2 public int findMaxPathScore(int[][] edges, boolean[] online, long k) {
3 int n = online.length;
4
5 // Build the adjacency list, keeping only edges whose endpoints are
6 // both online. Nodes 0 and n-1 are guaranteed online, so a route in
7 // the filtered graph is exactly a route with online intermediates.
8 List<int[]>[] graph = new ArrayList[n];
9 Arrays.setAll(graph, key -> new ArrayList<>());
10 int usable = 0;
11 int[] costs = new int[edges.length];
12 for (int[] edge : edges) {
13 if (online[edge[0]] && online[edge[1]]) {
14 graph[edge[0]].add(new int[] {edge[1], edge[2]});
15 costs[usable++] = edge[2];
16 }
17 }
18
19 // No usable edge means node n-1 cannot be reached at all.
20 if (usable == 0) {
21 return -1;
22 }
23
24 // The score of any route equals one of its edge costs, so the
25 // sorted distinct usable costs are the candidate answers.
26 costs = Arrays.copyOf(costs, usable);
27 Arrays.sort(costs);
28 int unique = 0;
29 for (int i = 0; i < usable; i++) {
30 if (i == 0 || costs[i] != costs[i - 1]) {
31 costs[unique++] = costs[i];
32 }
33 }
34
35 // Binary search the largest edge cost that still admits a valid route.
36 int answer = -1;
37 int lo = 0, hi = unique - 1;
38 while (lo <= hi) {
39 int mid = (lo + hi) >>> 1;
40 if (feasible(graph, n, k, costs[mid])) {
41 answer = costs[mid]; // record and try a larger guess
42 lo = mid + 1;
43 } else {
44 hi = mid - 1; // too strict; try a smaller guess
45 }
46 }
47 return answer;
48 }
49
50 // Dijkstra restricted to edges with cost >= threshold. Returns true if
51 // some route from node 0 to node n-1 has total cost at most k.
52 private boolean feasible(List<int[]>[] graph, int n, long k, int threshold) {
53 long[] distance = new long[n];
54 Arrays.fill(distance, Long.MAX_VALUE);
55 distance[0] = 0;
56
57 // Min-heap ordered by distance so far; entries are {distance, node}.
58 PriorityQueue<long[]> minHeap = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
59 minHeap.offer(new long[] {0, 0});
60
61 while (!minHeap.isEmpty()) {
62 long[] current = minHeap.poll();
63 long dist = current[0];
64 int node = (int) current[1];
65
66 // Skip stale entries whose recorded distance is outdated.
67 if (dist > distance[node]) {
68 continue;
69 }
70
71 // Every pushed distance already respects the budget, so
72 // reaching the target means a valid route exists.
73 if (node == n - 1) {
74 return true;
75 }
76
77 for (int[] next : graph[node]) {
78 int neighbor = next[0];
79 int cost = next[1];
80 // Edges cheaper than the current guess are forbidden.
81 if (cost < threshold) {
82 continue;
83 }
84 long newDist = dist + cost;
85 // Discard routes that already exceed the budget k.
86 if (newDist <= k && newDist < distance[neighbor]) {
87 distance[neighbor] = newDist;
88 minHeap.offer(new long[] {newDist, neighbor});
89 }
90 }
91 }
92 return distance[n - 1] <= k;
93 }
94}
951class Solution {
2public:
3 int findMaxPathScore(vector<vector<int>>& edges, vector<bool>& online, long long k) {
4 int n = online.size();
5
6 // Build the adjacency list, keeping only edges whose endpoints are
7 // both online. Nodes 0 and n-1 are guaranteed online, so a route in
8 // the filtered graph is exactly a route with online intermediates.
9 vector<vector<pair<int, int>>> graph(n);
10 vector<int> costs;
11 for (const auto& edge : edges) {
12 if (online[edge[0]] && online[edge[1]]) {
13 graph[edge[0]].push_back({edge[1], edge[2]});
14 costs.push_back(edge[2]);
15 }
16 }
17
18 // No usable edge means node n-1 cannot be reached at all.
19 if (costs.empty()) {
20 return -1;
21 }
22
23 // The score of any route equals one of its edge costs, so the
24 // sorted distinct usable costs are the candidate answers.
25 sort(costs.begin(), costs.end());
26 costs.erase(unique(costs.begin(), costs.end()), costs.end());
27
28 // Dijkstra restricted to edges with cost >= threshold. Returns true
29 // if some route from node 0 to node n-1 has total cost at most k.
30 auto feasible = [&](int threshold) -> bool {
31 vector<long long> dist(n, LLONG_MAX);
32 dist[0] = 0;
33 // Min-heap ordered by distance so far; entries are {distance, node}.
34 priority_queue<pair<long long, int>, vector<pair<long long, int>>,
35 greater<pair<long long, int>>> minHeap;
36 minHeap.push({0, 0});
37 while (!minHeap.empty()) {
38 auto [d, u] = minHeap.top();
39 minHeap.pop();
40 // Skip stale entries whose recorded distance is outdated.
41 if (d > dist[u]) {
42 continue;
43 }
44 // Every pushed distance already respects the budget, so
45 // reaching the target means a valid route exists.
46 if (u == n - 1) {
47 return true;
48 }
49 for (auto [v, cost] : graph[u]) {
50 // Edges cheaper than the current guess are forbidden.
51 if (cost < threshold) {
52 continue;
53 }
54 long long nd = d + cost;
55 // Discard routes that already exceed the budget k.
56 if (nd <= k && nd < dist[v]) {
57 dist[v] = nd;
58 minHeap.push({nd, v});
59 }
60 }
61 }
62 return dist[n - 1] <= k;
63 };
64
65 // Binary search the largest edge cost that still admits a valid route.
66 int answer = -1;
67 int lo = 0, hi = costs.size() - 1;
68 while (lo <= hi) {
69 int mid = (lo + hi) / 2;
70 if (feasible(costs[mid])) {
71 answer = costs[mid]; // record and try a larger guess
72 lo = mid + 1;
73 } else {
74 hi = mid - 1; // too strict; try a smaller guess
75 }
76 }
77 return answer;
78 }
79};
801// Minimal binary min-heap of [distance, node] pairs used by the Dijkstra routine.
2class MinHeap {
3 private heap: [number, number][] = [];
4
5 isEmpty(): boolean {
6 return this.heap.length === 0;
7 }
8
9 // Insert a new pair and restore the heap order by sifting it up.
10 push(value: [number, number]): void {
11 this.heap.push(value);
12 let index = this.heap.length - 1;
13 while (index > 0) {
14 const parent = (index - 1) >> 1;
15 if (this.heap[parent][0] <= this.heap[index][0]) {
16 break;
17 }
18 [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
19 index = parent;
20 }
21 }
22
23 // Remove and return the pair with the smallest distance.
24 pop(): [number, number] {
25 const top = this.heap[0];
26 const last = this.heap.pop()!;
27 if (this.heap.length > 0) {
28 this.heap[0] = last;
29 let index = 0;
30 while (true) {
31 const left = index * 2 + 1;
32 const right = index * 2 + 2;
33 let smallest = index;
34 if (left < this.heap.length && this.heap[left][0] < this.heap[smallest][0]) {
35 smallest = left;
36 }
37 if (right < this.heap.length && this.heap[right][0] < this.heap[smallest][0]) {
38 smallest = right;
39 }
40 if (smallest === index) {
41 break;
42 }
43 [this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
44 index = smallest;
45 }
46 }
47 return top;
48 }
49}
50
51function findMaxPathScore(edges: number[][], online: boolean[], k: number): number {
52 const n = online.length;
53
54 // Build the adjacency list, keeping only edges whose endpoints are both
55 // online. Nodes 0 and n-1 are guaranteed online, so a route in the
56 // filtered graph is exactly a route with online intermediates.
57 const graph: [number, number][][] = Array.from({ length: n }, () => []);
58 const costSet = new Set<number>();
59 for (const [u, v, cost] of edges) {
60 if (online[u] && online[v]) {
61 graph[u].push([v, cost]);
62 costSet.add(cost);
63 }
64 }
65
66 // No usable edge means node n-1 cannot be reached at all.
67 if (costSet.size === 0) {
68 return -1;
69 }
70
71 // The score of any route equals one of its edge costs, so the sorted
72 // distinct usable costs are the candidate answers.
73 const costs = Array.from(costSet).sort((a, b) => a - b);
74
75 // Dijkstra restricted to edges with cost >= threshold. Returns true if
76 // some route from node 0 to node n-1 has total cost at most k. Distances
77 // stay at most k <= 5 * 10^13, safely below Number.MAX_SAFE_INTEGER.
78 const feasible = (threshold: number): boolean => {
79 const dist: number[] = new Array(n).fill(Infinity);
80 dist[0] = 0;
81 const minHeap = new MinHeap();
82 minHeap.push([0, 0]);
83 while (!minHeap.isEmpty()) {
84 const [d, u] = minHeap.pop();
85 // Skip stale entries whose recorded distance is outdated.
86 if (d > dist[u]) {
87 continue;
88 }
89 // Every pushed distance already respects the budget, so
90 // reaching the target means a valid route exists.
91 if (u === n - 1) {
92 return true;
93 }
94 for (const [v, cost] of graph[u]) {
95 // Edges cheaper than the current guess are forbidden.
96 if (cost < threshold) {
97 continue;
98 }
99 const nd = d + cost;
100 // Discard routes that already exceed the budget k.
101 if (nd <= k && nd < dist[v]) {
102 dist[v] = nd;
103 minHeap.push([nd, v]);
104 }
105 }
106 }
107 return dist[n - 1] <= k;
108 };
109
110 // Binary search the largest edge cost that still admits a valid route.
111 let answer = -1;
112 let lo = 0;
113 let hi = costs.length - 1;
114 while (lo <= hi) {
115 const mid = (lo + hi) >> 1;
116 if (feasible(costs[mid])) {
117 answer = costs[mid]; // record and try a larger guess
118 lo = mid + 1;
119 } else {
120 hi = mid - 1; // too strict; try a smaller guess
121 }
122 }
123 return answer;
124}
125Time and Space Complexity
Time Complexity: O((n + m) · log n · log m)
Let n be the number of nodes and m the number of edges.
-
Filtering and sorting: Building the adjacency list scans the edges once,
O(m). Sorting the distinct usable costs takesO(m log m). -
Binary search: The candidate answers are the distinct usable edge costs, at most
mvalues, so the search performsO(log m)feasibility tests. -
Each feasibility test: One Dijkstra run over the filtered graph. Every edge is relaxed at most once per run and each heap operation costs
O(log)of the heap size, givingO((n + m) log n)per test.
Multiplying the per-test cost by the number of tests dominates the total: O((n + m) · log n · log m). With n <= 5 * 10⁴ and m <= 10⁵, this is roughly 10⁷ elementary operations, comfortable for the limits.
Space Complexity: O(n + m)
The adjacency list stores every usable edge once (O(n + m)), the distance array holds one 64-bit value per node (O(n)), the sorted cost array holds at most m values (O(m)), and the heap never exceeds O(m) entries.
Pattern Learn more about how to find time and space complexity quickly.
Common Pitfalls
Pitfall 1: Maximizing the bottleneck first, then checking the budget
A tempting shortcut is to solve the classic maximum-bottleneck problem — find the route whose cheapest edge is largest, ignoring totals — and then verify that this one route fits the budget k. That answers a different question. The bottleneck-optimal route and the budget-respecting routes can be entirely different paths.
Example 1 shows the failure directly: edges = [[0,1,5],[1,3,10],[0,2,3],[2,3,4]], k = 10. The bottleneck-optimal route is 0 → 1 → 3 with score min(5, 10) = 5, but its total is 15 > 10. Checking only that route and returning -1 (or worse, returning 5) is wrong; the correct answer is 3 via 0 → 2 → 3.
Solution: Fix the score threshold first, then minimize the total under that threshold. For each binary-search guess x, run a shortest-path computation over edges costing at least x and compare the cheapest total against k. The two objectives must be handled in this order because feasibility is monotone in x, while "best bottleneck" alone says nothing about totals.
Pitfall 2: Treating the check as plain reachability, or overflowing 32-bit totals
Two closely related mistakes hide in the feasibility test. The first is forgetting the budget entirely: reaching node n - 1 is not enough, the route must also cost at most k. With edges = [[0,1,7]] and k = 6, node 1 is reachable, but the only route costs 7 > 6, so the answer is -1, not 7. If your Dijkstra returns "yes" the moment it pops the target, make sure over-budget distances were never pushed in the first place:
nd = d + cost if nd <= k and nd < dist[v]: # budget check happens here dist[v] = nd heapq.heappush(heap, (nd, v))
The second is arithmetic range. A route can traverse up to 10⁵ edges of cost up to 10⁹, so totals reach 10¹⁴, and k itself goes up to 5 * 10¹³. Both exceed a 32-bit integer. In Java and C++, store distances in long / long long; note that the function signature already passes k as a 64-bit value.
Pitfall 3: Routing through offline nodes
Running Dijkstra on the raw edge list, without removing offline nodes, silently accepts forbidden routes. With edges = [[0,1,5],[1,2,5]], online = [true, false, true], and k = 10, the unfiltered graph offers the route 0 → 1 → 2 with total 10 <= k and score 5 — but node 1 is offline, so no valid route exists and the correct answer is -1.
Solution: Drop an edge unless both endpoints are online, before any traversal:
for u, v, cost in edges: if online[u] and online[v]: graph[u].append((v, cost))
Because nodes 0 and n - 1 are guaranteed online, this filter enforces exactly the "all intermediate nodes online" rule — no special-casing of the endpoints is needed during the search.
Ready to land your dream job?
Unlock your dream job with a 5-minute quiz for a personalized study roadmap!
Get My RoadmapWhat's the relationship between a tree and a graph?
Recommended Readings
https assets algo monster cover_photos Binary_Search svg Binary Search Intuition Binary search is an efficient array search algorithm It works by narrowing down the search range by half each time If you have looked up a word in a physical dictionary you've already used binary search in real life Let's
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
https assets algo monster cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could be disconnected A tree
Want a Structured Path to Master System Design Too? Don’t Miss This!