Show problems as
Classic problem #3620HardArrayBinary SearchDynamic ProgrammingGraph TheoryTopological SortHeap (Priority Queue)Shortest Path

Network Recovery Pathways

Real-world version: Fibre Restoration Grade
Tracked in this browser only
Read Network Recovery Pathways on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A carrier is bringing a backbone back up. Stations are numbered from 0 to n - 1, where n is the length of online, and online[i] says whether station i is powered up. Traffic may pass through a station only when that station is powered up, and that includes the two ends of the run.

links[t] = [u, v, w] is a one-way fibre from station u to station v with u < v. The number w is that fibre's grade, and splicing better fibre costs more, so restoring that link also draws w credits. Two stations may be joined by more than one fibre.

A run is a sequence of links leading from station 0 to station n - 1. Restoring a run draws the total of the grades of its links, and the carrier has budget credits to spend, so a run is affordable when that total is at most budget. The rating of a run is the smallest grade among its links, because the run is only as good as its worst fibre.

Return the largest rating over all affordable runs whose stations are all powered up. Every grade is at least 1, so return -1 when no such run exists.

Examples

Example 1

Input
links = [[0, 1, 10], [1, 3, 10], [0, 2, 3], [2, 3, 3]], online = [true, true, true, true], budget = 10
Output
3

The run through station 2 restores two links of grade 3 for 6 credits and rates 3, which is within the budget of 10 credits.

Example 2

Input
links = [[0, 1, 10], [1, 3, 10], [0, 2, 3], [2, 3, 3]], online = [true, true, true, true], budget = 20
Output
10

The run through station 1 restores two links of grade 10 for 20 credits and rates 10, which is exactly the budget.

Example 3

Input
links = [[0, 2, 6]], online = [true, true, true], budget = 0
Output
-1

The only run needs 6 credits and no credits are available, so nothing can be restored.

Constraints

  • 2 <= n == online.length <= 10^4
  • 1 <= links.length <= 5 * 10^4
  • links[t].length == 3
  • 0 <= u < v < n
  • 1 <= w <= 10^6
  • 0 <= budget <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_link_grade(links: list[list[int]], online: list[bool], budget: int) -> int:
Java
public int bestLinkGrade(int[][] links, boolean[] online, long budget)

More on the same topics