Find the closest marked node

Array Graph Theory Heap (Priority Queue) Shortest Path

65.4% acceptance

Mar 31, 2026

You are given a positive integer n which is the number of nodes of a 0-indexed directed weighted graph and a 0-indexed 2D array edges where edges[i] = [ui, vi, wi] indicates that there is an edge from node ui to node vi with weight wi. You are also given a node s and a node array marked; your task is to find the minimum distance from s to any of the nodes in marked. Return an integer denoting the minimum distance from s to any node in marked or -1 if there are no paths from s to any of the marked nodes.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_distance(n: i32, edges: Vec<Vec<i32>>, s: i32, marked: Vec<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));
    }
    let mut dist = vec![i64::MAX; n];
    dist[s as usize] = 0;
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0i64, s as usize)));
    while let Some(Reverse((cost, u))) = heap.pop() {
      if cost > dist[u] { continue; }
      for &(v, w) in &adj[u] {
        if cost + w < dist[v] {
          dist[v] = cost + w;
          heap.push(Reverse((cost + w, v)));
        }
      }
    }
    let result = marked.iter().map(|&m| dist[m as usize]).min().unwrap_or(i64::MAX);
    if result == i64::MAX { -1 } else { result as i32 }
  }
}