LeetCode743、网络延迟时间

INF = 100000  # 用于表示一个非常大的数，作为初始的最短距离

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        # 创建一个邻接表，用于存储每个节点的相邻节点及对应的路径权重
        neighbor_dic = defaultdict(list)
        for a, b, w in times:
            # 将边 (a -> b) 和对应的权重 w 加入邻接表
            neighbor_dic[a].append((b, w))  
        
        # 初始化一个列表 dist，用于记录从源节点 k 到每个节点的最短距离
        # 初始时，所有节点的距离都设置为 INF（表示尚未访问或不可达）
        dist = [INF] * (n+1)

        # 初始化一个最小堆，用于在Dijkstra算法中提取当前已知最短路径的节点
        # 堆中元素是 (当前时间, 当前节点) 元组
        heap = [(0, k)]

        # 进行Dijkstra（类似BFS）
        while heap:
            # 从堆中弹出当前时间最小的节点
            cur_time, cur_node = heappop(heap)
            
            # 如果当前节点的已记录最短时间比当前时间更小，说明已经找到更优的路径
            # 因此可以跳过当前节点
            if cur_time > dist[cur_node]:
                continue
            
            # 更新从源节点 k 到当前节点的最短时间
            dist[cur_node] = cur_time
            
            # 遍历当前节点的所有相邻节点
            for next_node, next_weight in neighbor_dic[cur_node]:
                # 计算通过当前节点到达相邻节点所需的时间
                next_time = cur_time + next_weight
                
                # 如果通过当前节点到达相邻节点的时间比之前记录的最短时间更短
                # 则更新相邻节点的最短时间，并将其加入堆中以便进一步探索
                if next_time < dist[next_node]:
                    heappush(heap, (next_time, next_node))
        
        # 找到从源节点 k 到所有节点的最短路径中的最大值
        ans = max(dist[1:])
        
        # 如果最大值小于 INF，说明所有节点都可达，返回最大值作为网络延迟时间
        # 否则返回 -1，表示有节点无法到达
        return ans if ans < INF else -1