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

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

        source = 1

        destination = n

        adj = defaultdict(set)

        for u, v in edges:

            adj[u].add(v)
            adj[v].add(u)

        dist1 = [-1]*(n+1)
        dist2 = [-1]*(n+1)

        que = deque([[0,source]])

        while que:

            for i in range(len(que)):

                curr_weight, node = que.popleft()

                # If signal is red wait unti signal becomes green
                if (curr_weight // change)%2:

                    curr_weight = (curr_weight // change + 1)*change

                curr_weight += time

                for adjacent in adj[node]:

                    if dist1[adjacent] == -1:

                        dist1[adjacent] = curr_weight

                        que.append([curr_weight, adjacent])

                    elif dist2[adjacent] == -1 and curr_weight != dist1[adjacent]:

                        dist2[adjacent] = curr_weight
                        que.append([curr_weight, adjacent])
                        if adjacent == destination:

                            return dist2[adjacent]

        return  dist2[adjacent]






















        dist1 = [INF]*(n+1)
        dist2 = [INF]*(n+1)

        dist1[source] = 0

        min_heap = list()
        heappush(min_heap,[0, 1])

        freq = [0]*(n+1)

        while min_heap:

            curr_weight, node = heappop(min_heap)

            # If signal is red wait unti signal becomes green
            if (curr_weight // change)%2:

                curr_weight = (curr_weight // change + 1)*change

            curr_weight += time

            for adjacent in adj[node]:
                
                if freq[adjacent] == 2:
                    continue

                if curr_weight  < dist1[adjacent]:
                    
                    dist2[adjacent] = dist1[adjacent]

                    dist1[adjacent] = curr_weight

                    heappush(min_heap,[curr_weight, adjacent])

                if curr_weight < dist2[adjacent] and dist1[adjacent] != curr_weight:

                    dist2[adjacent] = curr_weight

                    heappush(min_heap,[curr_weight, adjacent])
        print(dist1,dist2)
        return dist2[n]
                


















        dist1 = [math.inf] * (n + 1)
        dist2 = [math.inf] * (n + 1)

        freq = [0] * (n + 1)
        
        min_heap = [(0, 1)]

        dist1[1] = 0
        
        while min_heap:

            curr_weight, node = heapq.heappop(min_heap)
            freq[node] += 1
            
            
            # If signal is red wait unti signal becomes green
            if (curr_weight // change)%2:

                curr_weight = (curr_weight // change + 1)*change

            curr_weight += time
            
            for neighbor in adj[node]:
                
                if freq[neighbor] == 2:
                    continue
                
                # Update distances
                if dist1[neighbor] > curr_weight:
                    
                    dist2[neighbor] = dist1[neighbor]
                    dist1[neighbor] = curr_weight
                    heapq.heappush(min_heap, (curr_weight, neighbor))
                    
                elif dist2[neighbor] > curr_weight and dist1[neighbor] != curr_weight:
                    dist2[neighbor] = curr_weight
                    heapq.heappush(min_heap, (curr_weight, neighbor))
        
        return dist2[n]
    
        # Each vertex has  weight equal to time minutes
        # Signal chnages after every change minutes

        
        
        
        
        
        
        
        
        
        
        
        
        vis = set()

        parent = [0]*(n+1)
        parent[0] = -1
        while min_heap:

            curr_weight, node = heappop(min_heap)


            if node in vis:
                continue

            vis.add(node)

            # If signal is red wait unti signal becomes green
            if (curr_weight // change)%2:

                curr_weight = (curr_weight//change + 1)*change

            for adjacent in adj[node]:
                
                total = curr_weight + time

                if total < dist[adjacent]:
                    
                    dist[adjacent] = total
                    heappush(min_heap,[total, adjacent])
                    parent[adjacent] = node

        # minimum time path is dist[n]
        
        path = list()
        node = n
        while parent[node] != -1:

            path.append(node)

            node = parent[node]

        path.reverse()
        print(path,"original")
        smallest = INF

        for i in range(len(path)-1):

            # Check if there exists a node x between path[i] and path[i+1]
            
            for node in range(0,n+1):
                
                # Via node (edges + 1)
                if node not in [path[i],path[i+1]] and node in adj[path[i]] and node in adj[path[i+1]]:
                    # print("node",node)
                    path.insert(i+1, node)
                    smallest = node
                    break

            # We have two nodes through which we can bypas this node
            # Can I skip this node ?
            if i>0 and i < len(path)-2:
            
                flag = False
                for adjacent in adj[path[i-1]]:
                    if adjacent  == path[i]:
                        continue
                    for adjacent2 in adj[adjacent]:
                        
                        for adjacent3 in adj[adjacent2]:

                            if adjacent3 == path[i+1]:

                                flag = True
                                # print("True",adjacent,adjacent2,adjacent3,path,i)
                                smallest = adjacent
                                path[i] = adjacent
                                path.insert(i+1,adjacent2)

                            if flag:
                                break
                            # print(adjacent,adjacent2,adjacent3,path[i+1],path[i-1])
                        if flag:
                            break
                    if flag:
                        break

            if smallest != INF:

                break
      
        if smallest == INF:
            # Edges + 2
            # Add first and second node as repetative
            path.insert(2,path[0])
            path.insert(3,path[1])

        print(path,"modified")

        cost = 0

        for i in range(1,len(path)):
            
            if (cost // change) % 2:
                cost = (cost//change + 1)*change
            
            cost += time
            # print(path[i],cost)
        
        # 1:[2,3]
        # 2:[1,4]
        # 3:[1,5]
        # 4:[2,5,6]
        # 5:[3,4]
        # 6:[4]

        return cost

1736