Minimum cost of a path with special roads

Array Graph Theory Heap (Priority Queue) Shortest Path

42.5% acceptance

Feb 25, 2026

700

You are given an array start where start = [startX, startY] represents your initial position (startX, startY) in a 2D space. You are also given the array target where target = [targetX, targetY] represents your target position (targetX, targetY). The cost of going from a position (x1, y1) to any other position in the space (x2, y2) is |x2 - x1| + |y2 - y1|. There are also some special roads. You are given a 2D array specialRoads where specialRoads[i] = [x1i, y1i, x2i, y2i, costi] indicates that the ith special road goes in one direction from (x1i, y1i) to (x2i, y2i) with a cost equal to costi. You can use each special road any number of times. Return the minimum cost required to go from (startX, startY) to (targetX, targetY).

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_cost(start: Vec<i32>, target: Vec<i32>, special_roads: Vec<Vec<i32>>) -> i32 {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;
    // Nodes: start(0), each special road endpoint x2,y2 (1..=n), target(n+1)
    // dist from current best position to target using Dijkstra
    // State: (x, y) -> best cost
    // Use a map from (x,y) -> dist
    let mut dist: std::collections::HashMap<(i32,i32), i32> = std::collections::HashMap::new();
    let sx = start[0]; let sy = start[1];
    let tx = target[0]; let ty = target[1];
    let manhattan = |x1: i32, y1: i32, x2: i32, y2: i32| (x1-x2).abs() + (y1-y2).abs();
    
    // heap: (cost, x, y)
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0i32, sx, sy)));
    dist.insert((sx, sy), 0);
    
    while let Some(Reverse((d, x, y))) = heap.pop() {
      if d > *dist.get(&(x, y)).unwrap_or(&i32::MAX) { continue; }
      // Try going directly to target
      let to_target = d + manhattan(x, y, tx, ty);
      let e = dist.entry((tx, ty)).or_insert(i32::MAX);
      if to_target < *e { *e = to_target; heap.push(Reverse((to_target, tx, ty))); }
      // Try each special road
      for r in &special_roads {
        let (x1, y1, x2, y2, cost) = (r[0], r[1], r[2], r[3], r[4]);
        let new_cost = d + manhattan(x, y, x1, y1) + cost;
        let e = dist.entry((x2, y2)).or_insert(i32::MAX);
        if new_cost < *e { *e = new_cost; heap.push(Reverse((new_cost, x2, y2))); }
      }
    }
    *dist.get(&(tx, ty)).unwrap()
  }
}