<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>

"""
Problem: we are given n traffic lights (i.e. from 1 to n, 
inclusive) and connections between light Li and Lj along 
with the time it takes to go rom Li to Lj. We are also 
given the the time it takes a given light Lk to change 
from its current light to green or red. We are being
asked to find the second minimum time to go from the 1st
light to the nth.

If we were simply trying to find the minimum time to go
from the 1st light to the nth, without any consideration
of each light changing time, we could simply use the
djikastra algorithm with only a priority queue but 
without a predecessor dictionary (as we won't need to
reconstruct the path from nth to 1st). As we pop a node
from the queue, we visit it if it was not visited before.
For each neightbor, we add it to the queue.

To find the second minimum, we can modify the algorithm
above so that we can skip the node popped from the queue 
which is equal to the nth light. Once we pop a second
node that is equal to the nth light, we would return
its cost instead. Note here that we can use BFS as well
to track all paths, but it would take much more space
saving all paths, especially since we don't need the 
exact path.

We need incoporate the light change time to finalize our
algorithm. When we pop the node from the queue, we will 
have the cost of reaching it as t_cost. As we are 
discovering its neighors, we would either increase the 
cost of reaching a given neightbor by the light change 
time if the light is red. Otherwise, we wouldn't increase 
it. If the l_change is the time it takes the light to 
change, the light will be green if math.ceil(t_cost / l_change) 
is odd. Otherwise it its even, it will be red.
"""

import math
import heapq
from collections import deque

class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
        graph = self.build_graph(n, edges)

        discovered1, discovered2 = self.init_discovered(n)

        heap = [(0, 1)]

        while len(heap) > 0:
            cost1, node = heapq.heappop(heap)

            if cost1 < discovered1[node]:
                discovered2[node] = discovered1[node]
                discovered1[node] = cost1
            elif cost1 < discovered2[node] and cost1 != discovered1[node]:
                discovered2[node] = cost1
            else:
                continue

            for neighbor in graph[node]:
                if (cost1 // change) % 2 == 0:
                    heapq.heappush(heap, (cost1 + time, neighbor))
                else:
                    wait = change - (cost1 % change)
                    heapq.heappush(heap, (cost1 + time + wait, neighbor))

        return discovered2[n]

    def build_graph(self, n: int, edges: List[List[int]]):
        graph = {i: [] for i in range(1, n+1)}
        
        for i, j in edges:
            graph[i].append(j)
            graph[j].append(i)
        
        return graph
    
    def init_discovered(self, n: int):
        discovered1 = {}
        discovered2 = {}

        for i in range(1, n+1):
            discovered1[i] = float('inf')
            discovered2[i] = float('inf')
        
        return discovered1, discovered2
        
27800