Minimum threshold path with limited heavy edges

37.9% acceptance

May 13, 2026

There is an undirected weighted graph with n nodes labeled from 0 to n - 1. The graph is represented by a 2D integer array edges, where each edge edges[i] = [ui, vi, wi] indicates that there is an undirected edge between nodes ui and vi with weight wi. You are also given integers source, target and k. A threshold value determines whether an edge is considered light or heavy: An edge is light if its weight is less than or equal to threshold. An edge is heavy if its weight is greater than threshold. A path from source to target is valid if it contains at most k heavy edges. Return the minimum integer threshold such that at least one valid path exists from source to target. If no such path exists, return -1.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_threshold(n: i32, edges: Vec<Vec<i32>>, source: i32, target: i32, k: i32) -> i32 {
    if source == target { return 0; }
    let n = n as usize;
    let mut adj: Vec<Vec<(usize, i32)>> = vec![Vec::new(); n];
    for e in &edges {
      let (u, v, w) = (e[0] as usize, e[1] as usize, e[2]);
      adj[u].push((v, w));
      adj[v].push((u, w));
    }
    let mut candidates: Vec<i32> = vec![0];
    for e in &edges {
      candidates.push(e[2]);
    }
    candidates.sort_unstable();
    candidates.dedup();
    let source = source as usize;
    let target = target as usize;
    let check = |t: i32| -> bool {
      use std::collections::VecDeque;
      let mut dist = vec![i32::MAX; n];
      dist[source] = 0;
      let mut deque: VecDeque<usize> = VecDeque::new();
      deque.push_back(source);
      while let Some(u) = deque.pop_front() {
        let du = dist[u];
        for &(v, w) in &adj[u] {
          let cost = if w <= t { 0 } else { 1 };
          let new_d = du + cost;
          if new_d < dist[v] {
            dist[v] = new_d;
            if cost == 0 { deque.push_front(v); } else { deque.push_back(v); }
          }
        }
      }
      dist[target] != i32::MAX && dist[target] <= k
    };
    let mut lo = 0usize;
    let mut hi = candidates.len();
    while lo < hi {
      let mid = (lo + hi) / 2;
      if check(candidates[mid]) {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    if lo < candidates.len() { candidates[lo] } else { -1 }
  }
}