思路
首先将源点压入队列中,用st数组记录该节点是否更新过,避免队列中存储重复的节点。
每次更新时,将队列中的节点弹出,遍历该节点所有直接相连的节点,如果这些节点到源点的距离可以用弹出节点更新,
则更新相邻节点到源点的距离,并将相邻节点中没有更新过的节点压入队列中。
代码 + 注释
n, m = map(int, input().split())
N = n + 1
from collections import defaultdict, deque
g = defaultdict(list)
dmax = 1 << 30
dist = [dmax] * N
st = [False] * N
for i in range(m):
a, b, c = map(int, input().split())
g[a].append([b, c])
def spfa():
dist[1] = 0
q = deque()
q.append(1)
st[1] = True
while q:
i = q.popleft()
st[i] = False
for j, d in g[i]:
if dist[j] > dist[i] + d:
dist[j] = dist[i] + d
if not st[j]:
q.append(j)
st[j] = True
return dist[n]
if spfa() == dmax:
print('impossible')
else:
print(dist[n])