AcWing 851. SPFA PYTHON
原题链接
简单
作者:
Gyp
,
2020-03-14 19:06:37
,
所有人可见
,
阅读 609
import collections
n, m = map(int, input().split())
st = [False for _ in range(n+1)]
dist = [float("inf") for _ in range(n+1)]
g = collections.defaultdict(list)
for _ in range(m):
a, b, w = map(int, input().split())
g[a].append([b, w])
def spfa():
q, dist[1], st[1] = [1], 0, True
while len(q) != 0:
a = q.pop(0)
st[a] = False
for b, w in g[a]:
if dist[b] > dist[a] + w:
dist[b] = dist[a] + w
if st[b] == False:
q.append(b)
spfa()
print(dist[n] if dist[n] != float("inf") else "impossible")