1
from heapq import heappop, heappush
2
from collections import defaultdict
3

4

5
class Solution:
6
    def secondMinimum(
7
        self, n: int, edges: List[List[int]], time: int, change: int
8
    ) -> int:
9
        G = defaultdict(list)
10
        dist = defaultdict(set)
11
        for v, w in edges:
12
            G[v].append(w)
13
            G[w].append(v)
14
        h = [(0, 1)]
15
        res = []
16
        while h:
17
            d, v = heappop(h)
18
            if len(dist[v]) > 1:
19
                continue
20
            if d in dist[v]:
21
                continue
22
            dist[v].add(d)
23
            q, r = divmod(d, change)
24
            if q % 2 == 1:
25
                d += change - r
26
            for w in G[v]:
27
                if w == n:
28
                    if res:
29
                        if d + time not in res:
30
                            return d + time
31
                    else:
32
                        res.append(d + time)
33
                if len(dist[w]) < 2:
34
                    heappush(h, (d + time, w))