思路
更新k次,每次更新使用上次更新结束后的dist数组避免出现串联
每次更新遍历所有的边,用起点到源点的距离加上边权更新终点到源点的距离。
代码 + 注释
n, m, k = map(int, input().split())
N = n + 1
e = []
for i in range(m):
e.append(list(map(int, input().split())))
dmax = 1 << 30
dist = [dmax] * N
def bellman_fold():
dist[1] = 0
for i in range(k):
last = dist.copy() # 避免更新出现串联
for j in e:
a, b, c = j
dist[b] = min(dist[b], last[a] + c) # 松弛操作,只用上一次的结果更新,注意是last(a) 和 dist(b)
return dist[n]
if bellman_fold() > dmax // 2:
print('impossible')
else:
print(dist[n])