Second minimum time to reach destination

Breadth-First Search Graph Theory Shortest Path

62.4% acceptance

Feb 25, 2026

1319

A city is represented as a bi-directional connected graph with n vertices where each vertex is labeled from 1 to n (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. The time taken to traverse any edge is time minutes. Each vertex has a traffic signal which changes its color from green to red and vice versa every change minutes. All signals change at the same time. You can enter a vertex at any time, but can leave a vertex only when the signal is green. You cannot wait at a vertex if the signal is green. The second minimum value is defined as the smallest value strictly larger than the minimum value. For example the second minimum value of [2, 3, 4] is 3, and the second minimum value of [2, 2, 4] is 4. Given n, edges, time, and change, return the second minimum time it will take to go from vertex 1 to vertex n. Notes: You can go through any vertex any number of times, including 1 and n. You can assume that when the journey starts, all signals have just turned green.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn second_minimum(n: i32, edges: Vec<Vec<i32>>, time: i32, change: i32) -> i32 {
    let n = n as usize;
    let mut adj = vec![vec![]; n + 1];
    for e in &edges {
      let (u, v) = (e[0] as usize, e[1] as usize);
      adj[u].push(v);
      adj[v].push(u);
    }

    // BFS tracking minimum and second-minimum hop counts per node
    let mut dist1 = vec![i32::MAX; n + 1];
    let mut dist2 = vec![i32::MAX; n + 1];
    dist1[1] = 0;
    let mut queue = std::collections::VecDeque::new();
    queue.push_back((1usize, 0i32));

    while let Some((u, d)) = queue.pop_front() {
      let nd = d + 1;
      for &v in &adj[u] {
        if nd < dist1[v] {
          dist2[v] = dist1[v];
          dist1[v] = nd;
          queue.push_back((v, nd));
        } else if nd > dist1[v] && nd < dist2[v] {
          dist2[v] = nd;
          queue.push_back((v, nd));
        }
      }
    }

    // Compute actual time for a given number of hops (with traffic lights)
    let compute_time = |hops: i32| -> i32 {
      let mut t = 0i32;
      for _ in 0..hops {
        if (t / change) % 2 == 1 {
          t = (t / change + 1) * change;
        }
        t += time;
      }
      t
    };

    compute_time(dist2[n])
  }
}