# Second Minimum Time to Reach Destination
**Difficulty:** HARD
[External](https://leetcode.com/problems/second-minimum-time-to-reach-destination)
Canonical: https://scaleengineer.com/dsa/problems/second-minimum-time-to-reach-destination
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Graph
---
## Problem
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**.

**Example 1:**

![](https://assets.glich.co/dsa/second-minimum-time-to-reach-destination/image0.png) ![](https://assets.glich.co/dsa/second-minimum-time-to-reach-destination/image1.png) 

**Input:** n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5
**Output:** 13
**Explanation:**
The figure on the left shows the given graph.
The blue path in the figure on the right is the minimum time path.
The time taken is:
- Start at 1, time elapsed=0
- 1 -> 4: 3 minutes, time elapsed=3
- 4 -> 5: 3 minutes, time elapsed=6
Hence the minimum time needed is 6 minutes.

The red path shows the path to get the second minimum time.
- Start at 1, time elapsed=0
- 1 -> 3: 3 minutes, time elapsed=3
- 3 -> 4: 3 minutes, time elapsed=6
- Wait at 4 for 4 minutes, time elapsed=10
- 4 -> 5: 3 minutes, time elapsed=13
Hence the second minimum time is 13 minutes.      

**Example 2:**

![](https://assets.glich.co/dsa/second-minimum-time-to-reach-destination/image2.png) 

**Input:** n = 2, edges = [[1,2]], time = 3, change = 2
**Output:** 11
**Explanation:**
The minimum time path is 1 -> 2 with time = 3 minutes.
The second minimum time path is 1 -> 2 -> 1 -> 2 with time = 11 minutes.

**Constraints:**

* `2 <= n <= 104`
* `n - 1 <= edges.length <= min(2 * 104, n * (n - 1) / 2)`
* `edges[i].length == 2`
* `1 <= ui, vi <= n`
* `ui != vi`
* There are no duplicate edges.
* Each vertex can be reached directly or indirectly from every other vertex.
* `1 <= time, change <= 103`

# Approaches
## Modified Breadth-First Search
This approach uses a modified Breadth-First Search (BFS) to explore the graph. Since the edge weights (travel times) are not uniform due to potential waiting times at traffic signals, a standard BFS on nodes is insufficient. Instead, we perform a search on the state space `(vertex, time)`. We maintain two arrays, `dist1` and `dist2`, to keep track of the minimum and second minimum time to reach each vertex. A standard queue is used to manage the states to visit. While functionally correct, this method can be inefficient as it doesn't prioritize exploring paths with shorter total times, which can lead to exploring many suboptimal paths.
**Time:** O(N * E) in the worst case. A vertex can be enqueued multiple times if better paths are found. This is characteristic of SPFA-like algorithms and can be much slower than Dijkstra's on certain graphs. · **Space:** O(N + E), where N is the number of vertices and E is the number of edges. This is for storing the adjacency list, distance arrays, and the queue. In the worst case, the queue can hold a large number of states.
**Pros:** Conceptually simpler than Dijkstra's algorithm as it uses a basic queue data structure.; Relatively easy to implement.
**Cons:** Can be significantly less efficient than a priority-queue-based approach, potentially leading to a 'Time Limit Exceeded' error on larger or more complex graph structures.; It may explore many redundant paths because it doesn't prioritize states with lower travel times, leading to re-computation when a shorter path to an already visited node is found later.
### Explanation
This method adapts the BFS algorithm, which is typically used for unweighted graphs, to solve this problem. The state in our search is a pair `(vertex, time)`. We use a queue to process these states in a first-in, first-out manner.

We maintain two arrays, `dist1` and `dist2`, to store the shortest and second shortest times to every vertex. Initially, `dist1[1]` is 0, and all other distances are infinity.

We start by pushing `(1, 0)` into the queue. In each step, we extract a `(vertex, time)` pair, calculate the time to reach its neighbors (including waiting for green lights), and update the `dist1` and `dist2` arrays if we find a shorter or a new second-shorter path. If an update occurs, the new `(neighbor, newTime)` state is added to the queue.

This process is similar to the Shortest Path Faster Algorithm (SPFA). Its main drawback is that it might re-process vertices many times if shorter paths are discovered late in the search, making its worst-case performance poor compared to Dijkstra's algorithm.

```java
import java.util.*;

class Solution {
    public int secondMinimum(int n, int[][] edges, int time, int change) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        int[] dist1 = new int[n + 1];
        int[] dist2 = new int[n + 1];
        Arrays.fill(dist1, Integer.MAX_VALUE);
        Arrays.fill(dist2, Integer.MAX_VALUE);

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{1, 0}); // {node, time}
        dist1[1] = 0;

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int u = curr[0];
            int currentTime = curr[1];

            int waitTime = 0;
            if ((currentTime / change) % 2 == 1) { // Red light
                waitTime = change - (currentTime % change);
            }
            int newTime = currentTime + waitTime + time;

            for (int v : adj.get(u)) {
                if (newTime < dist1[v]) {
                    dist2[v] = dist1[v];
                    dist1[v] = newTime;
                    q.offer(new int[]{v, newTime});
                } else if (dist1[v] < newTime && newTime < dist2[v]) {
                    dist2[v] = newTime;
                    q.offer(new int[]{v, newTime});
                }
            }
        }
        return dist2[n];
    }
}
```
### Algorithm
1.  **Graph Representation**: Build an adjacency list to represent the city's connections.
2.  **Distance Arrays**: Initialize two arrays, `dist1` and `dist2`, of size `n+1`. `dist1[i]` will store the minimum time to reach vertex `i`, and `dist2[i]` will store the second minimum time. Initialize all values to infinity, except for `dist1[1] = 0`.
3.  **Queue Initialization**: Use a standard queue (e.g., `LinkedList`) and add the starting state, which is vertex 1 at time 0: `(1, 0)`.
4.  **BFS Traversal**: While the queue is not empty, dequeue a state `(u, currentTime)`.
5.  **Calculate Arrival Time at Neighbors**: For the current vertex `u` and `currentTime`:
    a.  Determine if you need to wait for a green light. The signal is green during intervals `[0, change)`, `[2*change, 3*change)`, etc. If `(currentTime / change)` is odd, the light is red, and you must wait until the time is `(currentTime / change + 1) * change`.
    b.  Calculate the `newTime` to reach a neighbor `v` as `departureTime + time`.
6.  **Update Distances and Enqueue**: For each neighbor `v` of `u`:
    a.  If `newTime` is less than `dist1[v]`, you've found a new shortest path. Update `dist1[v] = newTime` and the old `dist1[v]` becomes the new `dist2[v]`. Enqueue the new state `(v, newTime)`.
    b.  If `newTime` is greater than `dist1[v]` but less than `dist2[v]`, you've found a new second shortest path. Update `dist2[v] = newTime` and enqueue `(v, newTime)`.
7.  **Result**: After the queue is empty, `dist2[n]` will contain the second minimum time to reach the destination.

## Modified Dijkstra's Algorithm
This approach adapts Dijkstra's algorithm, which is ideal for finding the shortest paths in a graph with non-negative edge weights. The key is to use a priority queue to always expand the search from the vertex that can be reached in the minimum amount of time so far. This ensures that we find the shortest path to each vertex first. To find the second minimum time, we augment the algorithm to keep track of the two shortest times (`dist1` and `dist2`) to reach each vertex. By processing states in increasing order of time, this method efficiently prunes the search space and avoids the redundant computations of the BFS-based approach.
**Time:** O(E log N). Each edge relaxation may add an item to the priority queue. Since we only process each node for its first and second shortest paths, the number of pushes is proportional to E. Each priority queue operation takes O(log N) or O(log E) time. · **Space:** O(N + E), where N is the number of vertices and E is the number of edges. This space is used for the adjacency list, distance arrays, and the priority queue.
**Pros:** Highly efficient and guaranteed to find the optimal solution.; The use of a priority queue effectively prunes the search space, avoiding redundant calculations.
**Cons:** Slightly more complex to implement due to the use of a priority queue.; The logic for handling two distances per node adds a small amount of overhead compared to a standard Dijkstra's implementation.
### Explanation
This is the most efficient and standard way to solve this kind of shortest path problem. We model the problem on a graph where the nodes are the vertices and edge weights are dynamic based on arrival times.

Dijkstra's algorithm uses a priority queue to guarantee that we always explore the path with the currently known minimum total time. This is crucial for efficiency. We modify it to find two distinct shortest paths.

We maintain `dist1` and `dist2` arrays. The priority queue stores `(vertex, time)` pairs and prioritizes those with the smallest time. We start with `(1, 0)`.

When we extract a state `(u, currentTime)` from the priority queue, we know that `currentTime` is the shortest possible time for one of the paths to `u` among all paths not yet finalized. We then calculate the time to reach its neighbors. If this `newTime` offers a better `dist1` or `dist2` for a neighbor `v`, we update the distances and add `(v, newTime)` to the priority queue. A key optimization is to ignore any state `(u, currentTime)` if `currentTime > dist2[u]`, as we have already found two shorter paths to `u`.

Once we extract the destination `n` from the priority queue for the second time with a distinct time value, that time is our answer.

```java
import java.util.*;

class Solution {
    public int secondMinimum(int n, int[][] edges, int time, int change) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        int[] dist1 = new int[n + 1];
        int[] dist2 = new int[n + 1];
        Arrays.fill(dist1, Integer.MAX_VALUE);
        Arrays.fill(dist2, Integer.MAX_VALUE);

        // PriorityQueue stores {node, time}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.offer(new int[]{1, 0});
        dist1[1] = 0;

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int u = curr[0];
            int currentTime = curr[1];

            if (u == n && dist2[n] != Integer.MAX_VALUE) {
                return dist2[n];
            }

            // If we have already found two shorter paths to u, skip
            if (currentTime > dist2[u]) {
                continue;
            }

            // Calculate departure time considering traffic light
            int waitTime = 0;
            if ((currentTime / change) % 2 == 1) { // Red light
                waitTime = change - (currentTime % change);
            }
            int newTime = currentTime + waitTime + time;

            for (int v : adj.get(u)) {
                if (newTime < dist1[v]) {
                    dist2[v] = dist1[v];
                    dist1[v] = newTime;
                    pq.offer(new int[]{v, newTime});
                } else if (dist1[v] < newTime && newTime < dist2[v]) {
                    dist2[v] = newTime;
                    pq.offer(new int[]{v, newTime});
                }
            }
        }
        return -1; // Should not be reached
    }
}
```
### Algorithm
1.  **Graph Representation**: Build an adjacency list for the graph.
2.  **Distance Arrays**: Initialize `dist1` and `dist2` arrays to store the minimum and second minimum times for each vertex. Set all to infinity, except `dist1[1] = 0`.
3.  **Priority Queue**: Use a priority queue to store states `(vertex, time)`, ordered by `time`. Add the starting state `(1, 0)`.
4.  **Dijkstra's Traversal**: While the priority queue is not empty, extract the state `(u, currentTime)` with the smallest time.
5.  **Pruning**: If `currentTime` is already greater than `dist2[u]`, we can skip this state, as we've already found two better or equal paths to `u`.
6.  **Early Exit (Optional but efficient)**: If `u` is the destination `n` and we have found a time for it that is strictly greater than `dist1[n]`, this must be the second minimum time, so we can return it.
7.  **Calculate Arrival Time**: As in the BFS approach, calculate the `departureTime` from `u` considering traffic signal waits, and then the `newTime` to reach a neighbor `v`.
8.  **Update and Enqueue**: For each neighbor `v` of `u`:
    a.  If `newTime < dist1[v]`, update `dist1[v]` and `dist2[v]`, and push the new state `(v, newTime)` to the priority queue.
    b.  If `dist1[v] < newTime < dist2[v]`, update `dist2[v]` and push `(v, newTime)` to the priority queue.
9.  **Result**: The algorithm will find `dist2[n]`, which is the answer.

# Solutions
### Java

```java
class Solution {
public
  int secondMinimum(int n, int[][] edges, int time, int change) {
    List<Integer>[] g = new List[n + 1];
    Arrays.setAll(g, k->new ArrayList<>());
    for (int[] e : edges) {
      int u = e[0], v = e[1];
      g[u].add(v);
      g[v].add(u);
    }
    Deque<int[]> q = new LinkedList<>();
    q.offerLast(new int[]{1, 0});
    int[][] dist = new int[n + 1][2];
    for (int i = 0; i < n + 1; ++i) {
      Arrays.fill(dist[i], Integer.MAX_VALUE);
    }
    dist[1][1] = 0;
    while (!q.isEmpty()) {
      int[] e = q.pollFirst();
      int u = e[0], d = e[1];
      for (int v : g[u]) {
        if (d + 1 < dist[v][0]) {
          dist[v][0] = d + 1;
          q.offerLast(new int[]{v, d + 1});
        } else if (dist[v][0] < d + 1 && d + 1 < dist[v][1]) {
          dist[v][1] = d + 1;
          if (v == n) {
            break;
          }
          q.offerLast(new int[]{v, d + 1});
        }
      }
    }
    int ans = 0;
    for (int i = 0; i < dist[n][1]; ++i) {
      ans += time;
      if (i < dist[n][1] - 1 && (ans / change) % 2 == 1) {
        ans = (ans + change) / change * change;
      }
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int: g = defaultdict(set) for u, v in edges: g[u]. add(v) g[v]. add(u) q = deque([(1, 0)]) dist = [[inf] * 2 for _ in range(n + 1)] dist[1][1] = 0 while q: u, d = q . popleft() for v in g[u]: if d + 1 < dist[v][0]: dist[v][0] = d + 1 q . append((v, d + 1)) elif dist[v][0] < d + 1 < dist[v][1]: dist[v][1] = d + 1 if v == n: break q . append((v, d + 1)) ans = 0 for i in range(dist[n][1]): ans += time if i < dist[n][1] - 1 and (ans // change) % 2 == 1: ans = (ans + change) // change * change return ans

```