Second-Minimum Arrival Time With Periodic Signals
A courier traverses an unweighted city graph where every edge takes the same time, but periodic traffic signals force waiting. Find the strictly second-smallest time to travel from node 1 to node n.
Problem
A city has n nodes (1..n) connected by bidirectional edges; each edge takes time minutes to cross. Every change signals are green for change minutes then red for change minutes, synchronized at all nodes from t=0. You cannot leave a node while its signal is red (you wait until green). Return the second minimum time (strictly greater than the minimum) to go from node 1 to node n.
Input
Integers n, time, change, and an edge list edges.
Output
An integer: the strictly second-minimum arrival time.
Constraints
- 2 <= n <= 10^4
- n - 1 <= edges.length <= min(2*10^4, n*(n-1)/2)
- 1 <= time, change <= 10^3; the graph is connected with no self-loops or multi-edges.
Examples
Example 1
Input
n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5
Output
13
The minimum is 6; the strict second minimum, accounting for one red-signal wait, is 13.
Example 2
Input
n = 2, edges = [[1,2]], time = 3, change = 2
Output
11
Minimum 3; to get a strictly larger time you must loop back and forth, arriving at 11.