思路
将所有的点压入队列中,然后按照普通spfa进行更新,
因为出现负权回路的节点必然会一直更新,cnt数组统计该点到源点最短路的边数,当边数大于等于n时,说明出现负环。
代码 + 注释
n, m = map(int, input().split())
N = n + 1
from collections import deque, defaultdict
g = defaultdict(list)
dmax = 1 << 30
dist = [dmax] * N
cnt = [0] * N
st = [False] * N
for i in range(m):
a, b, c = map(int, input().split())
g[a].append([b, c])
def spfa():
q = deque()
for i in range(1, n + 1):
q.append(i)
st[i] = 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
cnt[j] += 1
if cnt[j] >= n:
return True
if not st[j]:
q.append(j)
st[j] = True
return False
if spfa():
print('Yes')
else:
print('No')
cnt[j] += 1这一行是不是错了,应该时cnt[j] = cnt[i]+1吧