743.网络延迟时间

https://leetcode-cn.com/problems/network-delay-time/

一、Dijkstra

求k到所有节点的最短路径，返回其中最长的一条即可

class Solution:
    def networkDelayTime(self, times, n: int, k: int) -> int:
        #构建邻接表
        graph = {}
        for i in range(n+1):
            graph[i] = list()

        for time in times:
            f = time[0]
            t = time[1]
            w = time[2]
            graph[f].append((t, w))    #（邻节点，权重）一同写入邻接表
        # 定义：distTo[i] 的值就是节点 start 到达节点 i 的最短路径权重，为求最短距离，初始值设为无穷大
        distTo = [sys.maxsize] * (n+1)  
        distTo[k] = 0
        # 用作最小堆（优先队列），堆内存储tuple（源点到节点i距离，i）。堆以tuple[0]（距离）排序，每次优先取出源点到i点距离最小的节点i
        pq = []
        heapq.heappush(pq, (0, k))
        while pq:
            curDistFromStart, curNodeId = heapq.heappop(pq)     #从堆中取出
            if curDistFromStart > distTo[curNodeId]:
                continue
            #比较所有邻节点
            for neigh in graph[curNodeId]:
                # neigh存储（邻节点，权重）
                nextNodeId = neigh[0]
                distToNextNode = distTo[curNodeId] + neigh[1]
                if distToNextNode < distTo[nextNodeId]:   #有更短的则更新
                    distTo[nextNodeId] = distToNextNode
                    heapq.heappush(pq, (distToNextNode, nextNodeId))
        res = -1
        #求k到终点距离的最大值
        for i in range(1, n+1):
            res = max(res, distTo[i])
        return -1 if res == sys.maxsize else res