Find shortest path with k hops

Graph Theory Heap (Priority Queue) Shortest Path

68.7% acceptance

Mar 31, 2026

You are given a positive integer n which is the number of nodes of a 0-indexed undirected weighted connected graph and a 0-indexed 2D array edges where edges[i] = [ui, vi, wi] indicates that there is an edge between nodes ui and vi with weight wi. You are also given two nodes s and d, and a positive integer k, your task is to find the shortest path from s to d, but you can hop over at most k edges. In other words, make the weight of at most k edges 0 and then find the shortest path from s to d. Return the length of the shortest path from s to d with the given condition.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

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