思路
1- 首先将源点和源点距离压入堆中,注意修改dist数组
2- 每次从堆中弹出一个节点和该节点到源点的距离,判断该点是否更新过,没有更新过的节点则更新该节点直接相邻的节点到源点的距离,然后将更行的相邻节点及距离压入堆中
堆优化的过程是找出没有更新过的节点中距离源点最近的节点。
代码 + 注释
n, m = map(int, input().split())
N = n + 1
from collections import defaultdict
from heapq import heappush, heappop
graph = defaultdict(list)
dmax = 1 << 30
dist = [dmax] * N
st = [False] * N
def dijkstra():
dist[1] = 0 # 不能忘记修改
h = []
heappush(h, [0, 1])
while h:
_, i = heappop(h)
if st[i]:
continue
st[i] = True
for item in graph[i]:
j, d = item # j 是与节点 i 直接相连的节点, d 是节点 i 和节点 j 之间的距离
if dist[j] > dist[i] + d:
dist[j] = dist[i] + d
heappush(h, [dist[j], j])
if dist[n] == dmax:
return -1
return dist[n]
for i in range(m):
a, b, c = map(int, input().split())
graph[a].append([b, c])
print(dijkstra())
%%%