2045. 到达目的地的第二短时间

import heapq
from collections import defaultdict


def dijkstra(edges, f, t):
    g = defaultdict(list)
    for l, r, c in edges:
        g[l].append((c, r))

    # dist records the min value of each node in heap.
    q, seen, dist = [(0, f)], set(), {f: 0}
    while len(q) > 0:
        cost, v1 = heapq.heappop(q)
        if v1 in seen:
            continue

        seen.add(v1)
        if v1 == t:
            return cost

        for c, v2 in g.get(v1, ()):
            if v2 in seen:
                continue
            # Not every edge will be calculated. Edges which can improve the value of node in heap will be useful.
            if v2 not in dist or cost + c < dist[v2]:
                dist[v2] = cost + c
                heapq.heappush(q, (cost + c, v2))
    return float("inf")

from collections import defaultdict, deque
from typing import List, Tuple


class Solution:
    def secondMinimum(self, n: int, edges: List[Tuple[int, int]], time: int, change: int) -> int:
        cost = self.dijkstra2nd(edges, 1, n)
        if cost == float('inf'):
            return -1

        ans = 0
        for _ in range(cost):
            if ans % (2 * change) >= change:
                ans += change - (ans % (2 * change) - change)
            ans += time

        return ans

    @staticmethod
    def dijkstra2nd(edges: List[Tuple[int, int]], f: int, t: int):
        g = defaultdict(list)
        for l, r in edges:
            g[l].append(r)
            g[r].append(l)

        # dist records the min value of each node in heap.
        # dist2nd records the 2nd min value of each node in heap
        q, dist, dist2nd = deque([(0, f)]), {f: 0}, {f: float('inf')}
        while len(q) > 0 and dist2nd.get(t, float('inf')) == float('inf'):
            cost, v1 = q.popleft()

            for v2 in g.get(v1, ()):
                if v2 not in dist or cost + 1 < dist[v2]:
                    dist[v2] = cost + 1
                    q.append((cost + 1, v2))
                elif dist[v2] < cost + 1 < dist2nd.get(v2, float('inf')):
                    dist2nd[v2] = cost + 1
                    q.append((cost + 1, v2))

        return dist2nd[t]