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

# I'm giving up. Finding minimum and subminimum at once seems to be too slow. I found an alternative solution, where you find all minimal paths from 1 to n, and then go through them to see, if any neigbour has the same distance to 1. If so, path length is x+1, otherwise x+2, and then you continue with wizardry due to time and changes. This will need to wait for a moment, when I have more sanity to spend.

from collections import defaultdict

class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
        roads = defaultdict(set)
        for a, b in edges:
            roads[a].add(b)
            roads[b].add(a)

        visited = set()
        to_be_visited = {1}
        min_path = {1: 0}

        while to_be_visited:
            visited |= to_be_visited
            new_to_be_visited = set()
            for i in to_be_visited:
                for j in roads[i]:
                    if j not in visited:
                        new_to_be_visited.add(j)
                        min_path[j] = min_path[i] + 1
            to_be_visited = new_to_be_visited

        to_be_visited = {n}
        found = False
        while to_be_visited and not found:
            new_to_be_visited = set()
            for i in to_be_visited:
                for j in roads[i]:
                    if min_path[i] == min_path[j]:
                        found = True
                    if min_path[i] == min_path[j] + 1:
                        new_to_be_visited.add(j)
            to_be_visited = new_to_be_visited

        n = min_path[n] + (1 if found else 2)

        # return 0

        # vis_nodes = {1: [0, 2]}
        # unvis_nodes = {1}

        # max_path = 1000000
        # cont = True
        # while unvis_nodes and cont:
        #     node = min(unvis_nodes, key=lambda x: vis_nodes[x])
        #     unvis_nodes.remove(node)

        #     if max_path - 1 <= vis_nodes[node][0]:
        #         break

        #     new_t = [t + 1 for t in vis_nodes[node]]
        #     for new_node in roads[node]:
        #         new_node_ts = vis_nodes.get(new_node)
        #         if new_node_ts is None:
        #             vis_nodes[new_node] = [t + 1 for t in vis_nodes[node]]
        #             unvis_nodes.add(new_node)
        #         else:
        #             if new_node_ts[1] > new_t[0] > new_node_ts[0]:
        #                 new_node_ts[1] = new_t[0]
        #                 unvis_nodes.add(new_node)
        #             if new_node_ts[1] > new_t[1] > new_node_ts[0]:
        #                 new_node_ts[1] = new_t[1]
        #         if new_node == n:
        #             max_path = min(max_path, vis_nodes[new_node][1])
        #             if vis_nodes[new_node][1] - vis_nodes[new_node][0] == 1:
        #                 cont = False
        #     # print(node, vis_nodes)

        # n = vis_nodes[n][1] - 1
        n -= 1
        change2 = 2 * change
        result = 0

        while time // change2:
            result += change2 * (n + 1)
            time = time - change2
        if time // change:
            result += change2 * n + time
            return result
        if not time:
            return result
        intervs = [time]
        for i in range(2, 1000):
            if i * time < change:
                intervs.append(i * time)
            else:
                intervs.append(i * time)
                break
        
        while n >= len(intervs):
            n -= len(intervs)
            result += change2
        result += intervs[n]

        return result
1671