Minimum time to reach destination in directed graph

Graph Theory Heap (Priority Queue) Shortest Path

45.5% acceptance

Feb 25, 2026

101

You are given an integer n and a directed graph with n nodes labeled from 0 to n - 1. This is represented by a 2D array edges, where edges[i] = [ui, vi, starti, endi] indicates an edge from node ui to vi that can only be used at any integer time t such that starti <= t <= endi. You start at node 0 at time 0. In one unit of time, you can either: Wait at your current node without moving, or Travel along an outgoing edge from your current node if the current time t satisfies starti <= t <= endi. Return the minimum time required to reach node n - 1. If it is impossible, return -1.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_time(n: i32, edges: Vec<Vec<i32>>) -> i32 {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;
    let n = n as usize;
    // adj[u] = list of (v, start, end)
    let mut adj: Vec<Vec<(usize, i64, i64)>> = vec![vec![]; n];
    for e in &edges {
      adj[e[0] as usize].push((e[1] as usize, e[2] as i64, e[3] as i64));
    }
    let mut dist = vec![i64::MAX; n];
    dist[0] = 0;
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0i64, 0usize)));
    while let Some(Reverse((t, u))) = heap.pop() {
      if t > dist[u] { continue; }
      if u == n - 1 { return t as i32; }
      for &(v, s, e) in &adj[u] {
        if t <= e {
          let depart = t.max(s);
          let arrive = depart + 1;
          if arrive < dist[v] {
            dist[v] = arrive;
            heap.push(Reverse((arrive, v)));
          }
        }
      }
    }
    if dist[n - 1] == i64::MAX { -1 } else { dist[n - 1] as i32 }
  }
}