Formatted question description: https://leetcode.ca/all/2045.html

# 2045. Second Minimum Time to Reach Destination (Hard)

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] = [u`

denotes a bi-directional edge between vertex _{i}, v_{i}]`u`

and vertex _{i}`v`

. Every vertex pair is connected by _{i}**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:**

Input:n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5Output:13Explanation: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:**

Input:n = 2, edges = [[1,2]], time = 3, change = 2Output:11Explanation: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 <= 10`

^{4}`n - 1 <= edges.length <= min(2 * 10`

^{4}, n * (n - 1) / 2)`edges[i].length == 2`

`1 <= u`

_{i}, v_{i}<= n`u`

_{i}!= v_{i}- There are no duplicate edges.
- Each vertex can be reached directly or indirectly from every other vertex.
`1 <= time, change <= 10`

^{3}

**Similar Questions**:

- Network Delay Time (Medium)
- Find the City With the Smallest Number of Neighbors at a Threshold Distance (Medium)
- Number of Ways to Arrive at Destination (Medium)

## Solution 1. BFS

**Intuition**: If the shortest path from `1`

to `n`

is of length `L`

, find whether there is a path of length `L + 1`

by taking a detour. There is always a path of length `L + 2`

(by going back-and-forth).

```
// OJ: https://leetcode.com/problems/second-minimum-time-to-reach-destination/
// Time: O(N + E)
// Space: O(N + E)
// Ref: https://leetcode.com/problems/second-minimum-time-to-reach-destination/discuss/1525165/C%2B%2B-Two-BFS-with-detailed-explanation
class Solution {
public:
int secondMinimum(int n, vector<vector<int>>& E, int time, int change) {
vector<vector<int>> G(n);
for (auto &e : E) {
int u = e[0] - 1, v = e[1] - 1;
G[u].push_back(v);
G[v].push_back(u);
}
vector<int> dist(n, INT_MAX);
dist[n - 1] = 0;
queue<int> q{ {n - 1} };
while (q.size()) {
int u = q.front();
q.pop();
for (int v : G[u]) {
if (dist[v] != INT_MAX) continue;
dist[v] = 1 + dist[u];
q.push(v);
}
}
int len = dist[0] + 2; // Try to find a path of length `dist[0] + 1`
q.push(0);
bool found = false;
while (q.size() && !found) {
int u = q.front();
q.pop();
for (int v : G[u]) {
if (dist[v] == dist[u]) { // u and v are at the same layer of the shortest path, so dist[u] can be 1 + dist[u] by going to v first then u.
len--;
found = true;
break;
} else if (dist[v] == dist[u] - 1) q.push(v); // push the nodes on the next layer of the shortest path
}
}
int ans = 0;
for (int i = 0; i < len; ++i) {
ans += time;
if (i != len - 1 && ans / change % 2) ans = (ans / change + 1) * change;
}
return ans;
}
};
```

Or

```
// OJ: https://leetcode.com/problems/second-minimum-time-to-reach-destination/
// Time: O(N + E)
// Space: O(N + E)
// Ref: https://leetcode.com/problems/second-minimum-time-to-reach-destination/discuss/1525154/No-Dijkstra%3A-(n-%2B-1)-or-(n-%2B-2)
class Solution {
public:
int secondMinimum(int n, vector<vector<int>>& E, int time, int change) {
auto getTime = [&](int step) {
int ans = 0;
for (int i = 0; i < step; ++i) {
ans += time;
if (i != step - 1 && ans / change % 2) ans = (ans / change + 1) * change;
}
return ans;
};
vector<vector<int>> G(n);
for (auto &e : E) {
int u = e[0] - 1, v = e[1] - 1;
G[u].push_back(v);
G[v].push_back(u);
}
vector<int> dist(n, 10001);
queue<int> q{ {0} };
int step = 0;
while (q.size() && step <= dist[n - 1] + 1) {
int cnt = q.size();
while (cnt--) {
int u = q.front();
q.pop();
if (step == dist[u] || step > dist[u] + 1) continue; // Only visit node `u` if it haven't been visited or this visit takes only one more step than last time.
dist[u] = min(dist[u], step);
if (u == n - 1 && step == dist[n - 1] + 1) return getTime(step);
for (int v : G[u]) q.push(v);
}
++step;
}
return getTime(dist[n - 1] + 2);
}
};
```