大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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")
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/193704.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...