Network recovery pathways

Array Binary Search Dynamic Programming Graph Theory Topological Sort Heap (Priority Queue) Shortest Path

29.9% acceptance

Feb 25, 2026

136

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] = [ui, vi, costi] indicates a one-way communication from node ui to node vi with a recovery cost of costi. 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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn find_max_path_score(edges: Vec<Vec<i32>>, online: Vec<bool>, k: i64) -> i32 {
    use std::collections::BinaryHeap;
    let n = online.len();
    let mut adj: Vec<Vec<(usize, i64)>> = vec![vec![]; n];
    for e in &edges {
      let (u, v, c) = (e[0] as usize, e[1] as usize, e[2] as i64);
      if online[u] && (v == n - 1 || online[v]) {
        adj[u].push((v, c));
      }
    }
    // Dijkstra-like: maximize minimum edge cost subject to total cost <= k
    // State: (node, total_cost) -> max min_edge
    // Use a heap sorted by min_edge descending
    // dist[node] = (best_min_edge, min_total_cost_at_that_min_edge)
    // This is complex - use modified Dijkstra with state (node, total_cost)
    // Binary search on answer: can we reach n-1 with all edges >= mid and total cost <= k?
    // Collect all unique costs
    let mut all_costs: Vec<i64> = edges.iter().map(|e| e[2] as i64).collect();
    all_costs.sort_unstable();
    all_costs.dedup();
    // Binary search
    let check = |min_cost: i64| -> bool {
      // Dijkstra: min total cost to reach n-1 using only edges with cost >= min_cost
      let mut dist = vec![i64::MAX; n];
      dist[0] = 0;
      let mut heap = BinaryHeap::new();
      heap.push(std::cmp::Reverse((0i64, 0usize)));
      while let Some(std::cmp::Reverse((d, u))) = heap.pop() {
        if d > dist[u] { continue; }
        if u == n - 1 { return d <= k; }
        for &(v, c) in &adj[u] {
          if c >= min_cost {
            let nd = d + c;
            if nd < dist[v] {
              dist[v] = nd;
              heap.push(std::cmp::Reverse((nd, v)));
            }
          }
        }
      }
      dist[n - 1] != i64::MAX && dist[n - 1] <= k
    };
    if !check(0) { return -1; }
    let mut lo = 0usize;
    let mut hi = all_costs.len();
    while lo < hi {
      let mid = (lo + hi + 1) / 2;
      if check(all_costs[mid - 1]) { lo = mid; } else { hi = mid - 1; }
    }
    if lo == 0 { 0 } else { all_costs[lo - 1] as i32 }
  }
}