Second Minimum Time to Reach Destination

hard graph bfs shortest path

Problem

A connected undirected graph has n vertices (labeled 1..n); every edge takes time minutes to cross. Each vertex has a traffic signal that flips between green and red every change minutes (all in sync, all green at minute 0). You may leave a vertex only while its signal is green. Return the second minimum time (the smallest value strictly larger than the minimum) to travel from vertex 1 to vertex n.

Inputn = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5

Output13

Fastest path 1→4→5 takes 6 min. The second-fastest uses 3 edges (1→3→4→5); arriving at 4 at minute 6 the signal is red, so wait 4 min, then cross to 5: 6 + 4 + 3 = 13.

n (number of vertices)

edges (u-v, comma-separated)

time (per edge)

change (signal period)

from collections import deque

def second_minimum(n, edges, time, change):
    g = [[] for _ in range(n + 1)]
    for u, v in edges:
        g[u].append(v); g[v].append(u)
    dist1 = [float('inf')] * (n + 1)
    dist2 = [float('inf')] * (n + 1)
    dist1[1] = 0
    q = deque([(1, 1)])
    while q:
        node, freq = q.popleft()
        d = dist1[node] if freq == 1 else dist2[node]
        for nei in g[node]:
            if d + 1 < dist1[nei]:
                dist1[nei] = d + 1
                q.append((nei, 1))
            elif dist1[nei] < d + 1 < dist2[nei]:
                dist2[nei] = d + 1
                q.append((nei, 2))
    t = 0
    for _ in range(dist2[n]):
        if (t // change) % 2 == 1:
            t = (t // change + 1) * change
        t += time
    return t

function secondMinimum(n, edges, time, change) {
  const g = Array.from({ length: n + 1 }, () => []);
  for (const [u, v] of edges) { g[u].push(v); g[v].push(u); }
  const dist1 = new Array(n + 1).fill(Infinity);
  const dist2 = new Array(n + 1).fill(Infinity);
  dist1[1] = 0;
  const q = [[1, 1]];
  while (q.length) {
    const [node, freq] = q.shift();
    const d = freq === 1 ? dist1[node] : dist2[node];
    for (const nei of g[node]) {
      if (d + 1 < dist1[nei]) {
        dist1[nei] = d + 1;
        q.push([nei, 1]);
      } else if (dist1[nei] < d + 1 && d + 1 < dist2[nei]) {
        dist2[nei] = d + 1;
        q.push([nei, 2]);
      }
    }
  }
  let t = 0;
  for (let k = 0; k < dist2[n]; k++) {
    if (Math.floor(t / change) % 2 === 1) t = (Math.floor(t / change) + 1) * change;
    t += time;
  }
  return t;
}

int secondMinimum(int n, int[][] edges, int time, int change) {
    List<List<Integer>> g = new ArrayList<>();
    for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
    for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
    int[] dist1 = new int[n + 1], dist2 = new int[n + 1];
    Arrays.fill(dist1, Integer.MAX_VALUE);
    Arrays.fill(dist2, Integer.MAX_VALUE);
    dist1[1] = 0;
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[]{1, 1});
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int d = cur[1] == 1 ? dist1[cur[0]] : dist2[cur[0]];
        for (int nei : g.get(cur[0])) {
            if (d + 1 < dist1[nei]) {
                dist1[nei] = d + 1;
                q.add(new int[]{nei, 1});
            } else if (dist1[nei] < d + 1 && d + 1 < dist2[nei]) {
                dist2[nei] = d + 1;
                q.add(new int[]{nei, 2});
            }
        }
    }
    int t = 0;
    for (int k = 0; k < dist2[n]; k++) {
        if ((t / change) % 2 == 1) t = (t / change + 1) * change;
        t += time;
    }
    return t;
}

int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
    vector<vector<int>> g(n + 1);
    for (auto& e : edges) { g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); }
    vector<int> dist1(n + 1, INT_MAX), dist2(n + 1, INT_MAX);
    dist1[1] = 0;
    queue<pair<int,int>> q;
    q.push({1, 1});
    while (!q.empty()) {
        auto [node, freq] = q.front(); q.pop();
        int d = freq == 1 ? dist1[node] : dist2[node];
        for (int nei : g[node]) {
            if (d + 1 < dist1[nei]) {
                dist1[nei] = d + 1;
                q.push({nei, 1});
            } else if (dist1[nei] < d + 1 && d + 1 < dist2[nei]) {
                dist2[nei] = d + 1;
                q.push({nei, 2});
            }
        }
    }
    int t = 0;
    for (int k = 0; k < dist2[n]; k++) {
        if ((t / change) % 2 == 1) t = (t / change + 1) * change;
        t += time;
    }
    return t;
}

Explanation

Because every edge costs the same time, the fastest route is simply the one with the fewest edges. So a plain breadth-first search would give the minimum. The twist is that we need the second minimum — the smallest distinct travel time larger than the best.

Key insight: the second-minimum time corresponds to a path with strictly more edges than the minimum (waiting at a red light only ever increases time, and revisiting nodes adds edges). So we run a BFS that, for every vertex, remembers the two smallest edge-counts that reach it: dist1 (shortest) and dist2 (strictly larger second-shortest).

We push pairs (node, freq) into the queue, where freq tells whether this arrival used the shortest count (1) or the second count (2). When we relax a neighbor with a new count d+1: if it beats dist1[nei] we record it as the new shortest; otherwise if it is strictly between dist1[nei] and dist2[nei] we record it as the second-shortest. Each vertex is enqueued at most twice, so the BFS is linear.

Once we know dist2[n] (the number of edges on the second-best path), we replay those edges minute by minute. Before crossing each edge we check the signal: the period t / change being odd means the light is red, so we jump forward to the next green boundary. Then we add time for the crossing.

In the default example the minimum path 1→4→5 uses 2 edges (6 min), and the second path uses 3 edges. Replaying 3 edges with change = 5 forces one red-light wait at minute 6, giving 6 + 4 + 3 = 13.

Time: O(n + edges) Space: O(n + edges)