大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
Powered by:NEFU AB-IN
904. 虫洞
-
题意
见原题
-
思路
看是否有负环即可
- 别忘把所有点都入队
-
代码
''' Author: NEFU AB-IN Date: 2022-04-16 16:17:22 FilePath: \ACM\Acwing\904.py LastEditTime: 2022-04-16 16:17:23 ''' from collections import deque N = 550 INF = int(1e9) g = [[] for _ in range(N)] dist, st, cnt = [INF] * N, [0] * N, [0] * N def spfa(): q = deque() for i in range(1, n + 1): q.appendleft(i) st[i] = 1 dist[i] = 0 while q: u = q.pop() st[u] = 0 for v, w in g[u]: if dist[v] > dist[u] + w: dist[v] = dist[u] + w if st[v] == 0: st[v] = 1 q.appendleft(v) cnt[v] = cnt[u] + 1 if cnt[v] >= n: return 1 return 0 for _ in range(int(input())): g = [[] for _ in range(N)] dist, st, cnt = [INF] * N, [0] * N, [0] * N n, m, w = map(int, input().split()) for i in range(m): u, v, t = map(int, input().split()) g[u].append([v, t]) g[v].append([u, t]) for i in range(w): u, v, t = map(int, input().split()) g[u].append([v, -t]) if spfa(): print("YES") else: print("NO")
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/193704.html原文链接：https://javaforall.net
