Modify graph edge weights

Graph Theory Heap (Priority Queue) Shortest Path

55.6% acceptance

Feb 25, 2026

738

153

You are given an undirected weighted connected graph containing n nodes labeled from 0 to n - 1, and an integer array edges where edges[i] = [ai, bi, wi] indicates that there is an edge between nodes ai and bi with weight wi. Some edges have a weight of -1 (wi = -1), while others have a positive weight (wi > 0). Your task is to modify all edges with a weight of -1 by assigning them positive integer values in the range [1, 2 * 10^9] so that the shortest distance between the nodes source and destination becomes equal to an integer target. If there are multiple modifications that make the shortest distance between source and destination equal to target, any of them will be considered correct. Return an array containing all edges (even unmodified ones) in any order if it is possible to make the shortest distance from source to destination equal to target, or an empty array if it's impossible.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn modified_graph_edges(
    n: i32,
    edges: Vec<Vec<i32>>,
    source: i32,
    destination: i32,
    target: i32,
  ) -> Vec<Vec<i32>> {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;

    let n = n as usize;
    let src = source as usize;
    let dst = destination as usize;
    let target = target as i64;
    let m = edges.len();

    // Build adjacency list: adj[u] = list of (v, edge_index)
    let mut adj = vec![vec![]; n];
    for (i, e) in edges.iter().enumerate() {
      let a = e[0] as usize;
      let b = e[1] as usize;
      adj[a].push((b, i));
      adj[b].push((a, i));
    }

    // Dijkstra using adjacency list: O(E log V).
    // Edges with weight <= 0 in `wts` are treated as non-existent.
    let dijkstra = |wts: &[i64], from: usize| -> Vec<i64> {
      let mut dist = vec![i64::MAX / 2; n];
      dist[from] = 0;
      let mut heap = BinaryHeap::new();
      heap.push(Reverse((0i64, from)));
      while let Some(Reverse((d, u))) = heap.pop() {
        if d > dist[u] {
          continue;
        }
        for &(v, ei) in &adj[u] {
          let w = wts[ei];
          if w <= 0 {
            continue;
          }
          let nd = d + w;
          if nd < dist[v] {
            dist[v] = nd;
            heap.push(Reverse((nd, v)));
          }
        }
      }
      dist
    };

    let mut weights: Vec<i64> = edges.iter().map(|e| e[2] as i64).collect();

    // Check impossibility: if shortest path using only positive edges < target
    let d_pos = dijkstra(&weights, src);
    if d_pos[dst] < target {
      return vec![];
    }

    // Process each -1 edge.
    // Exclude edge i (set to 0, skipped by dijkstra) so ds/dt reflect
    // distances without it; remaining unprocessed -1 edges stay -1 and
    // are also skipped, giving correct one-sided distances.
    for i in 0..m {
      if weights[i] != -1 {
        continue;
      }
      weights[i] = 0;
      let ds = dijkstra(&weights, src);
      let dt = dijkstra(&weights, dst);
      weights[i] = -1;

      let a = edges[i][0] as usize;
      let b = edges[i][1] as usize;

      // Path: src->...->a --(w)--> b->...->dst  =>  ds[a] + w + dt[b] = target
      // Path: src->...->b --(w)--> a->...->dst  =>  ds[b] + w + dt[a] = target
      let w1 = target - ds[a] - dt[b];
      let w2 = target - ds[b] - dt[a];

      weights[i] = if w1 >= 1 {
        w1
      } else if w2 >= 1 {
        w2
      } else {
        1
      };
    }

    // Verify final shortest path = target
    let final_dist = dijkstra(&weights, src);
    if final_dist[dst] != target {
      return vec![];
    }

    edges
      .into_iter()
      .enumerate()
      .map(|(i, mut e)| {
        e[2] = weights[i] as i32;
        e
      })
      .collect()
  }
}