Minimum time to visit disappearing nodes

Array Graph Theory Heap (Priority Queue) Shortest Path

37.5% acceptance

Feb 23, 2026

217

There is an undirected graph of n nodes. You are given a 2D array edges, where edges[i] = [ui, vi, lengthi] describes an edge between node ui and node vi with a traversal time of lengthi units. Additionally, you are given an array disappear, where disappear[i] denotes the time when the node i disappears from the graph and you won't be able to visit it. Note that the graph might be disconnected and might contain multiple edges. Return the array answer, with answer[i] denoting the minimum units of time required to reach node i from node 0. If node i is unreachable from node 0 then answer[i] is -1.

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

    let mut dist = vec![i32::MAX; n];
    dist[0] = 0;
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0i32, 0usize)));

    while let Some(Reverse((d, u))) = heap.pop() {
      if d > dist[u] {
        continue;
      }
      for &(v, w) in &adj[u] {
        let nd = d + w;
        if nd < dist[v] && nd < disappear[v] {
          dist[v] = nd;
          heap.push(Reverse((nd, v)));
        }
      }
    }

    dist.iter()
      .enumerate()
      .map(|(i, &d)| if d < disappear[i] { d } else { -1 })
      .collect()
  }
}