Minimum cost to reach city with discounts

Graph Theory Heap (Priority Queue) Shortest Path

60.3% acceptance

Mar 31, 2026

246

No description available.

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 minimum_cost(n: i32, highways: Vec<Vec<i32>>, discounts: i32) -> i32 {
    let n = n as usize;
    let discounts = discounts as usize;
    let mut adj = vec![vec![]; n];
    for h in &highways {
      let u = h[0] as usize;
      let v = h[1] as usize;
      let w = h[2];
      adj[u].push((v, w));
      adj[v].push((u, w));
    }

    let cap = discounts.min(n);
    let mut dist = vec![vec![i32::MAX; cap + 1]; n];
    dist[0][0] = 0;
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0i32, 0usize, 0usize))); // (cost, node, discounts_used)

    while let Some(Reverse((cost, u, d))) = heap.pop() {
      if u == n - 1 {
        return cost;
      }
      if cost > dist[u][d] {
        continue;
      }
      for &(v, w) in &adj[u] {
        // without discount
        let nc = cost + w;
        if nc < dist[v][d] {
          dist[v][d] = nc;
          heap.push(Reverse((nc, v, d)));
        }
        // with discount
        if d < cap {
          let nc2 = cost + w / 2;
          if nc2 < dist[v][d + 1] {
            dist[v][d + 1] = nc2;
            heap.push(Reverse((nc2, v, d + 1)));
          }
        }
      }
    }

    -1
  }
}