AcWing 852. spfa判断负环-python
原题链接
简单
作者:
Actor丶
,
2020-02-22 15:28:57
,
所有人可见
,
阅读 794
def spfa():
dist = [0]*(n+1) # !!!注意:这里绝对不同用float("inf"),因为在比较dist距离时,dist[t]+w还是==float("inf"),因此不能更新距离
st = [False]*(n+1)
cnt = [0]*(n+1)
dist[1] = 0
queue = []
for i in range(1,n+1):
queue.append(i)
st[i] = True
while queue:
t = queue.pop() # !注意:与求1号点到n号点的出队顺序不同,因为判负环要分别从所有节点开始判断,所以元素pop的顺序对结果不产生影响;所以优先用O(1)复杂度的pop()
st[t] = False
if t not in graph: continue
for weight, node in graph[t]:
if dist[node]>dist[t]+weight:
dist[node] = dist[t]+weight
cnt[node] = cnt[t]+1
if cnt[node]>=n: return True
if not st[node]:
queue.append(node)
st[node] = True
return False
if __name__=="__main__":
n, m = map(int, input().split())
graph = {}
for i in range(m):
x, y, z = map(int, input().split())
if x not in graph:
graph[x] = [(z, y)]
else:
graph[x].append((z, y))
res = spfa()
# print(res)
print("Yes") if res else print("No")