Dijkstra 算法;

  1. 先构建邻接表
  2. 构建权重数组 cost,记录节点 1 到每个节点的距离
  3. 优先级队列,以节点 1 到该节点的距离作为优先级 遍历优先级队列中的节点, (1) 如果得到的 距离 w 大于 cost[节点 n] 的值则跳过 (2) 否则从 n 的邻接表中取出相连的节点 ne, 比较更新其 cost[ne],符合条件的进入优先级队列 (3) 直到队列为空,得出最终的 cost
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 顶点数
# @param m int整型 边数
# @param graph int整型二维数组 一维3个数据，表示顶点到另外一个顶点的边长度是多少​
# @return int整型
#
from queue import PriorityQueue 

class Solution:
    def findShortestPath(self , n: int, m: int, graph: List[List[int]]) -> int:
        # write code here
        adj = [[] for _ in range(n)]
        for i, j, w in graph:
            adj[i - 1].append([j - 1, w])
        cost = [float("inf") for _ in range(n)]
        q = PriorityQueue()
        q.put((0, 0))
        cost[0] = 0
        while not q.empty():
            w, n = q.get()
            if w > cost[n]:
                continue
            for ne, we in adj[n]:
                nw = w + we
                if cost[ne] > nw:
                    cost[ne] = nw
                    q.put((nw, ne))
        return cost[-1] if count[-1] != float("inf") else -1