Minimum cost to repair edges to traverse a graph

Binary Search Breadth-First Search Graph Theory

60.4% acceptance

Apr 3, 2026

You are given an undirected graph with n nodes labeled from 0 to n - 1. The graph consists of m edges represented by a 2D integer array edges, where edges[i] = [ui, vi, wi] indicates that there is an edge between nodes ui and vi with a repair cost of wi. You are also given an integer k. Initially, all edges are damaged. You may choose a non-negative integer money and repair all edges whose repair cost is less than or equal to money. All other edges remain damaged and cannot be used. You want to travel from node 0 to node n - 1 using at most k edges. Return an integer denoting the minimum amount of money required to make this possible, or return -1 if it is impossible.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(n: i32, edges: Vec<Vec<i32>>, k: i32) -> i32 {
    use std::collections::VecDeque;

    fn can_reach(graph: &[Vec<(usize, i32)>], threshold: i32, max_edges: i32) -> bool {
      let target = graph.len() - 1;
      let mut dist = vec![-1i32; graph.len()];
      let mut queue = VecDeque::new();

      dist[0] = 0;
      queue.push_back(0usize);

      while let Some(node) = queue.pop_front() {
        let next_distance = dist[node] + 1;
        if next_distance > max_edges {
          continue;
        }

        for &(next, cost) in &graph[node] {
          if cost > threshold || dist[next] != -1 {
            continue;
          }

          dist[next] = next_distance;
          if next == target {
            return true;
          }
          queue.push_back(next);
        }
      }

      false
    }

    let n = n as usize;
    let mut graph = vec![Vec::<(usize, i32)>::new(); n];
    let mut weights = Vec::with_capacity(edges.len());

    for edge in edges {
      let u = edge[0] as usize;
      let v = edge[1] as usize;
      let w = edge[2];
      graph[u].push((v, w));
      graph[v].push((u, w));
      weights.push(w);
    }

    weights.sort_unstable();
    weights.dedup();

    if !can_reach(&graph, *weights.last().unwrap(), k) {
      return -1;
    }

    let mut left = 0usize;
    let mut right = weights.len() - 1;

    while left < right {
      let mid = left + (right - left) / 2;
      if can_reach(&graph, weights[mid], k) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }

    weights[left]
  }
}