from math import inf import heapq from collections import defaultdict """ Dijkstra算法 构建邻接表graph 构建用来储存到起点最短长度的列表dict,用来存储需要加入判断的边的最小堆heap 整体思路:不断地去更新从起点到邻接点的最短距离 从起点(第一个发散点)开始,更新其邻接点到起点的距离 并将更新过(如果新的路径距离更短)的点和距离(到起点的最短距离)放入heap中 heap中放置的是与能与发散点集相连的所有点,以及这些点与起点的最短距离(存在部分不是最短距离的) 找到距离起点最近的点(heap中的)成为新的发散点 更新其邻接点到起点的最短距离 找到所有进入heap中的最短距离对应的点,成为新的发散点 如此循环,直到heap为空 heap为空意味着,所有点到起点的最短距离已经更新完毕 因为如果还有需要更新的点,那么heap就会加入新的元素,不会为空 此时dict中放置着从起点到达各个点的最短距离 注意,heap中的点可能会重复 比如:[1,3,3],[1,2,1],[2,3,1] heap的发展为[(0,1)]→[(1,2),(3,3)]→[(3,3)]→[(2,3),(3,3)] 此时heap中重复出现点3 所有要进行剪枝,即如果当前d!=dict[node],即当前距离不是最短距离,则逃过这个元素,操作heap中的下一个元素 """ n,m = map(int,input().split()) graph = defaultdict(list) for _ in range(m): u,v,w = map(int,input().split()) graph[u].append((v,w)) graph[v].append((u,w)) dist = [inf]*(5001) dist[1] = 0 heap = [(0,1)] while heap: d,node = heapq.heappop(heap) if d != dist[node]: continue for neighbor,w in graph[node]: new_dist = d + w if new_dist < dist[neighbor]: dist[neighbor] = new_dist heapq.heappush(heap,(new_dist,neighbor)) print(dist[n] if dist[n]!=inf else -1)