菜鸟的每日力扣系列——2045. 到达目的地的第二短时间

from collections import defaultdict, deque
from typing import List


def second_minimum(n: int, edges: List[List[int]], time: int, change: int) -> int:
    graph = defaultdict(list)  # 字典键存节点，值存与之相邻的节点组成的列表
    for e1, e2 in edges:
        graph[e1].append(e2)
        graph[e2].append(e1)
    distance = [[float('inf')] * 2 for _ in range(n+1)]
    distance[1][0] = 0  # 从1到1的最短路径为0
    # BFS 模版----------
    queue = deque()  # BFS队列
    queue.append((1, 0))  # 第一种路径情况入队
    while queue:
        node, dis = queue.popleft()  # 取出队头节点node，以及1到该节点的距离
        for y in graph[node]:  # 遍历与节点node相邻的节点
            d = dis + 1  # 表示1经过node再到y的路径长度
            # 维护最短路径
            if d < distance[y][0]:  # 如果比之前1到y的最短路径短就更新最短路径，将y和d入队
                distance[y][0] = d
                queue.append((y, d))
            # 维护次短路径
            elif distance[y][0] < d < distance[y][1]:  # 如果d比之前最短的路径长，但比次短路径短，更新次短路径
                distance[y][1] = d
                if y == n:  # 如果是节点n，已找到结果，跳出循环
                    break
                queue.append((y, d))
    # 计算次短时间
    res = 0
    for i in range(distance[n][1]):  # 1到n的次短路径是distance[n][1]
        res += time  # 加上通过一条边的时间
        # 当(res // change)为偶数时不会遇到红灯，不需要等待
        if i < distance[n][1] - 1 and (res // change) % 2:
            # distance[n][1] - 1是最后一次到达n，不需要等待
            res += (change - res % change)
    return res


n = 5
edges = [[1, 2], [1, 3], [1, 4], [3, 4], [4, 5]]
time = 3
change = 5
print(second_minimum(n, edges, time, change))  # 13