leetcode 每日1题

3112. 访问消失节点的最少时间

from heapq import heappop, heappush
from typing import List

class Solution:
    def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:
        # 创建邻接表
        adj = [[] for _ in range(n)]
        for u, v, length in edges:
            adj[u].append((v, length))
            adj[v].append((u, length))

        # 初始化优先队列，开始时只有起点0，时间为0
        pq = [(0, 0)]
        # 初始化答案列表，用于存储从起点到每个点的最短时间，初始设置为-1表示未访问
        answer = [-1] * n
        answer[0] = 0  # 起点的最短时间是0

        while pq:
            # 弹出当前最小的元素
            t, u = heappop(pq)
            # 如果当前点的时间不是已知的最短时间，则跳过（这是因为优先队列中可能有过时的条目）
            if t != answer[u]:
                continue
            # 遍历所有邻接点
            for v, length in adj[u]:
                # 计算到达邻接点v的时间
                new_time = t + length
                # 检查是否在消失时间之前，并且是否比已知时间更短
                if new_time < disappear[v] and (answer[v] == -1 or new_time < answer[v]):
                    # 如果条件满足，更新答案，并将新的时间和点推入优先队列
                    answer[v] = new_time
                    heappush(pq, (new_time, v))
        
        return answer