Minimum cost path with edge reversals

Graph Theory Heap (Priority Queue) Shortest Path

61.8% acceptance

Feb 25, 2026

456

You are given a directed, weighted graph with n nodes labeled from 0 to n - 1, and an array edges where edges[i] = [ui, vi, wi] represents a directed edge from node ui to node vi with cost wi. Each node ui has a switch that can be used at most once: when you arrive at ui and have not yet used its switch, you may activate it on one of its incoming edges vi -> ui, reverse that edge to ui -> vi and immediately traverse it. The reversal costs 2 * wi. Return the minimum total cost to travel from node 0 to node n - 1. If not possible, return -1.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(n: i32, edges: Vec<Vec<i32>>) -> i32 {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;
    let n = n as usize;
    // State: (node, switch_used)
    // At node u with switch_not_used: can traverse normal edges or use switch on incoming edge.
    // State space: (node, has_used_switch: bool)
    // 
    // Build adjacency lists:
    // Forward edges: u -> v at cost w (normal traversal)
    // Reverse edges: when at v with switch unused, can "reverse" edge u->v to go v->u at cost 2w.
    //   But the problem says: at node ui, you can reverse an incoming edge of ui.
    //   "incoming edge vi -> ui" reversed to "ui -> vi" traversed at cost 2*wi.
    //   So at node ui, you look at edges that come INTO ui (i.e., edges of form [vi, ui, wi]),
    //   pick one, reverse it, and traverse it (going from ui to vi at cost 2*wi).
    //   This uses ui's switch.
    
    // Build:
    // fwd[u] = list of (v, w): u -> v, cost w
    // rev_at[u] = list of (v, w): there's an edge v -> u, so at u can go to v at cost 2*w
    let mut fwd: Vec<Vec<(usize, i64)>> = vec![vec![]; n];
    let mut rev_at: Vec<Vec<(usize, i64)>> = vec![vec![]; n];
    
    for e in &edges {
      let (u, v, w) = (e[0] as usize, e[1] as usize, e[2] as i64);
      fwd[u].push((v, w));
      rev_at[v].push((u, w)); // at node v, can reverse to go to u at cost 2w
    }
    
    // Dijkstra – each node has its own switch (per-node, not global).
    // Since Dijkstra with non-negative weights settles each node at most once,
    // at-most-one-reversal-per-node is naturally ensured.
    // The switch can only be used when you *arrive* at a node, so the
    // starting node (0) cannot use its switch.
    let inf = i64::MAX / 2;
    let mut dist = vec![inf; n];
    dist[0] = 0;
    
    let mut heap: BinaryHeap<Reverse<(i64, usize)>> = BinaryHeap::new();
    heap.push(Reverse((0, 0)));
    
    while let Some(Reverse((cost, u))) = heap.pop() {
      if cost > dist[u] { continue; }
      // Normal forward edges
      for &(v, w) in &fwd[u] {
        let nc = cost + w;
        if nc < dist[v] {
          dist[v] = nc;
          heap.push(Reverse((nc, v)));
        }
      }
      // Use u's switch: reverse an incoming edge (allowed at any node including start)
      for &(v, w) in &rev_at[u] {
        let nc = cost + 2 * w;
        if nc < dist[v] {
          dist[v] = nc;
          heap.push(Reverse((nc, v)));
        }
      }
    }
    
    if dist[n-1] >= inf { -1 } else { dist[n-1] as i32 }
  }
}