<p>A city is represented as a <strong>bi-directional connected</strong> graph with <code>n</code> vertices where each vertex is labeled from <code>1</code> to <code>n</code> (<strong>inclusive</strong>). The edges in the graph are represented as a 2D integer array <code>edges</code>, where each <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> denotes a bi-directional edge between vertex <code>u<sub>i</sub></code> and vertex <code>v<sub>i</sub></code>. Every vertex pair is connected by <strong>at most one</strong> edge, and no vertex has an edge to itself. The time taken to traverse any edge is <code>time</code> minutes.</p>

<p>Each vertex has a traffic signal which changes its color from <strong>green</strong> to <strong>red</strong> and vice versa every&nbsp;<code>change</code> minutes. All signals change <strong>at the same time</strong>. You can enter a vertex at <strong>any time</strong>, but can leave a vertex <strong>only when the signal is green</strong>. You <strong>cannot wait </strong>at a vertex if the signal is <strong>green</strong>.</p>

<p>The <strong>second minimum value</strong> is defined as the smallest value<strong> strictly larger </strong>than the minimum value.</p>

<ul>
	<li>For example the second minimum value of <code>[2, 3, 4]</code> is <code>3</code>, and the second minimum value of <code>[2, 2, 4]</code> is <code>4</code>.</li>
</ul>

<p>Given <code>n</code>, <code>edges</code>, <code>time</code>, and <code>change</code>, return <em>the <strong>second minimum time</strong> it will take to go from vertex </em><code>1</code><em> to vertex </em><code>n</code>.</p>

<p><strong>Notes:</strong></p>

<ul>
	<li>You can go through any vertex <strong>any</strong> number of times, <strong>including</strong> <code>1</code> and <code>n</code>.</li>
	<li>You can assume that when the journey <strong>starts</strong>, all signals have just turned <strong>green</strong>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/09/29/e1.png" style="width: 200px; height: 250px;" /> &emsp; &emsp; &emsp; &emsp;<img alt="" src="https://assets.leetcode.com/uploads/2021/09/29/e2.png" style="width: 200px; height: 250px;" />
<pre>
<strong>Input:</strong> n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5
<strong>Output:</strong> 13
<strong>Explanation:</strong>
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 -&gt; 4: 3 minutes, time elapsed=3
- 4 -&gt; 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 -&gt; 3: 3 minutes, time elapsed=3
- 3 -&gt; 4: 3 minutes, time elapsed=6
- Wait at 4 for 4 minutes, time elapsed=10
- 4 -&gt; 5: 3 minutes, time elapsed=13
Hence the second minimum time is 13 minutes.      
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/09/29/eg2.png" style="width: 225px; height: 50px;" />
<pre>
<strong>Input:</strong> n = 2, edges = [[1,2]], time = 3, change = 2
<strong>Output:</strong> 11
<strong>Explanation:</strong>
The minimum time path is 1 -&gt; 2 with time = 3 minutes.
The second minimum time path is 1 -&gt; 2 -&gt; 1 -&gt; 2 with time = 11 minutes.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 10<sup>4</sup></code></li>
	<li><code>n - 1 &lt;= edges.length &lt;= min(2 * 10<sup>4</sup>, n * (n - 1) / 2)</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt;= n</code></li>
	<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>
	<li>There are no duplicate edges.</li>
	<li>Each vertex can be reached directly or indirectly from every other vertex.</li>
	<li><code>1 &lt;= time, change &lt;= 10<sup>3</sup></code></li>
</ul>

# 到达目的地的第二短时间

# 双向连通 -> 可來回
#  n 个节点，从 1 到 n 编号（包含 1 和 n)
#  edges[i] = [ui, vi] 表示一条节点 ui 和节点 vi 之间的双向连通边
#  每组节点对由 最多一条 边连通

#  每个节点都有一个交通信号灯，每 change 分钟改变一次，从绿色变成红色，再由红色变成绿色
#  所有信号灯都 同时 改变。
#  可以在 任何时候 进入某个节点，但是 只能 在节点 信号灯是绿色时 才能离开。
#  如果信号灯是  绿色 ，你 不能 在节点等待，必须离开。

#  第二小的值 是 严格大于 最小值的所有值中最小的值。
#  返回从节点 1 到节点 n 需要的 第二短时间 。

# Example 1:
# 上面的左图展现了给出的城市交通图。
# 右图中的蓝色路径是最短时间路径。
# 花费的时间是：
# - 从节点 1 开始，总花费时间=0
# - 1 -> 4：3 分钟，总花费时间=3
# - 4 -> 5：3 分钟，总花费时间=6
# 因此需要的最小时间是 6 分钟。

# 右图中的红色路径是第二短时间路径。
# - 从节点 1 开始，总花费时间=0
# - 1 -> 3：3 分钟，总花费时间=3
# - 3 -> 4：3 分钟，总花费时间=6
# - 在节点 4 等待 4 分钟，总花费时间=10
# - 4 -> 5：3 分钟，总花费时间=13
# 因此第二短时间是 13 分钟。    

# Example 2:
# 最短时间路径是 1 -> 2 ，总花费时间 = 3 分钟
# 第二短时间路径是 1 -> 2 -> 1 -> 2 ，总花费时间 = 11 分钟

# 找出從頂點1到頂點n的第二最短路徑的時間，考慮到交通信號燈的影響。
# 題目給定了每條邊的固定行駛時間，以及每個頂點的交通信號燈變換時間。
# 你可以在任何時候進入頂點，但只能在信號燈為綠燈時離開。

# 解題思路：
# 我們可以使用一個基於最短路徑的算法來求解這個問題，並且要考慮每個頂點可能有兩種不同的最短路徑時間，因此需要保存每個頂點的前兩個最短到達時間。

# 建構圖：將所有邊構造成鄰接列表。

# BFS/優先級隊列：使用廣度優先搜索（BFS）來遍歷圖，每當我們到達一個新頂點時，計算到達這個頂點所花的時間。
# 記錄兩個時間：對於每個頂點，我們需要記錄兩個時間：到達該頂點的最短時間和第二短時間。
# 如果這是到達該頂點的最短時間或第二最短時間，則更新相應的時間並將其加入隊列進行進一步擴展。

# 計算信號燈等待時間：每次移動到下一個頂點時，需要檢查當前時間是否處於紅燈階段。
# 如果當前時間點是紅燈，需要等到下一次綠燈才能離開，這時候需要計算等待的時間。

# 返回結果：當隊列處理完畢，返回從頂點1到頂點n的第二最短路徑的時間。

# 1 - n
# min_heap = [(current time, current node, visited count)]
# best[i][0] 是到達i的最短時間，best[i][1] 是第二短時間

import heapq
from collections import defaultdict, deque
class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
        # 建構圖
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        min_heap = [(0, 1)]  # (current time, current node, visited count)
        best = [[float('inf'), float('inf')] for _ in range(n + 1)]  # best[i][0] 是到達i的最短時間，best[i][1] 是第二短時間
        best[1][0] = 0

        while min_heap:
            cur_time, node = heapq.heappop(min_heap)

            for neighbor in graph[node]:
                # 計算移動到neighbor的下一個時間
                wait_time = cur_time // change
                if wait_time % 2 == 1:  # 如果當前是紅燈，則需要等待
                    cur_time = (wait_time + 1) * change
                
                next_time = cur_time + time

                if next_time < best[neighbor][0]:
                    best[neighbor][1] = best[neighbor][0]
                    best[neighbor][0] = next_time
                    heapq.heappush(min_heap, (next_time, neighbor))
                elif best[neighbor][0] < next_time < best[neighbor][1]:
                    best[neighbor][1] = next_time
                    heapq.heappush(min_heap, (next_time, neighbor))
        
        return best[n][1] if best[n][1] < float('inf') else -1
2189