Second Distinct Arrival Time with Synchronized Signals
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
You are given a connected, undirected graph whose vertices are numbered from `1` through `n`. Traversing any edge takes `time` minutes. Every vertex has the same traffic signal: all signals start green, then alternate between green and red every `change` minutes. You may enter a vertex at any time, but you may leave only while its signal is green. If it is green, you must leave immediately rather than wait. Starting at vertex `1` at time zero, return the second smallest distinct arrival time at vertex `n`. Routes may revisit vertices, including the endpoints, and two routes with the same arrival time count as one time.
```cpp
class Solution {
public:
int secondMinimum(int n, vector<vector<int>>& edges, int time, int change);
};
```
### Examples
**Example 1:**
```text
n = 2, edges = [[1,2]], time = 1, change = 3
Output: 3
Explanation: The second distinct walk is 1->2->1->2 and all three departures occur during green.
```
**Example 2:**
```text
n = 3, edges = [[1,2],[2,3],[1,3]], time = 2, change = 2
Output: 6
Explanation: Direct arrival takes 2. A two-edge route waits from time 2 to 4, then arrives at 6.
```
### Constraints
- `2 <= n <= 10^4`.
- `n-1 <= edges.length <= min(2*10^4,n*(n-1)/2)`.
- Valid distinct endpoints; no duplicate edges; the graph is connected.
- `1 <= time,change <= 1000`.
### Clarifying Questions
Equal minimum-time paths do not constitute a second distinct time. At an exact multiple of change the new signal color already applies. No wait is needed after final arrival.
```hint Inspect the structure
Do walks having the same number of edges necessarily have the same arrival time here?
```
### Reasoning checkpoints
- Find the second distinct arrival time rather than a second route with the same earliest time.
- Apply the mandatory departure rule correctly at both signal boundaries and intermediate visits.
- Allow repeated vertices and edges, and justify the result when the destination is reached more than once.
### Optional extensions
How would your approach change if the signals had different phase offsets at different vertices?
Overview: Second Distinct Arrival Time with Synchronized Signals. In a connected simple undirected graph labeled 1 through n, every edge takes time minutes. All signals begin green at time zero and alternate green/red every change minutes in synchrony. You may enter any time, must wait during red before leaving, and must leave immediately during green. Vertices, including endpoints, may be revisited. Return the smallest arrival time at n strictly greater than the minimum arrival time.