Minimum distance excluding one maximum weighted edge

46.2% acceptance

Mar 31, 2026

You are given a positive integer n and a 2D integer array edges, where edges[i] = [ui, vi, wi]. There is a weighted connected simple undirected graph with n nodes labeled from 0 to n - 1. Each [ui, vi, wi] in edges represents an edge between node ui and node vi with positive weight wi. The cost of a path is the sum of weights of the edges in the path, excluding the edge with the maximum weight. If there are multiple edges in the path with the maximum weight, only the first such edge is excluded. Return an integer representing the minimum cost of a path going from node 0 to node n - 1.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
  pub fn min_cost_excluding_max(n: i32, edges: Vec<Vec<i32>>) -> i64 {
    let n = n as usize;
    let mut adj = vec![vec![]; n];
    for e in &edges {
      let (u, v, w) = (e[0] as usize, e[1] as usize, e[2] as i64);
      adj[u].push((v, w));
      adj[v].push((u, w));
    }
    let mut dist = vec![[i64::MAX; 2]; n];
    let mut heap = BinaryHeap::new();
    dist[0][0] = 0;
    heap.push(Reverse((0i64, 0usize, 0u8)));
    while let Some(Reverse((cost, u, skip))) = heap.pop() {
      let s = skip as usize;
      if cost > dist[u][s] { continue; }
      if u == n - 1 && s == 1 { return cost; }
      for &(v, w) in &adj[u] {
        let nc = cost + w;
        if nc < dist[v][s] {
          dist[v][s] = nc;
          heap.push(Reverse((nc, v, skip)));
        }
        if s == 0 && cost < dist[v][1] {
          dist[v][1] = cost;
          heap.push(Reverse((cost, v, 1)));
        }
      }
    }
    dist[n - 1][1]
  }
}