904 虫洞(spfa找负环)
2021/11/3 23:14:11
本文主要是介绍904 虫洞(spfa找负环),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1. 问题描述:
农夫约翰在巡视他的众多农场时,发现了很多令人惊叹的虫洞。虫洞非常奇特,它可以看作是一条 单向 路径,通过它可以使你回到过去的某个时刻(相对于你进入虫洞之前)。农夫约翰的每个农场中包含 N 片田地,M 条路径(双向)以及 W 个虫洞。现在农夫约翰希望能够从农场中的某片田地出发,经过一些路径和虫洞回到过去,并在他的出发时刻之前赶到他的出发地。他希望能够看到出发之前的自己。请你判断一下约翰能否做到这一点。翰拥有的农场数量 F,以及每个农场的完整信息。已知走过任何一条路径所花费的时间都不超过 10000 秒,任何虫洞将他带回的时间都不会超过 10000 秒。
输入格式
第一行包含整数 F,表示约翰共有 F 个农场。对于每个农场,第一行包含三个整数 N,M,W。接下来 M 行,每行包含三个整数 S,E,T,表示田地 S 和 E 之间存在一条路径,经过这条路径所花的时间为 T。再接下来 W 行,每行包含三个整数 S,E,T,表示存在一条从田地 S 走到田地 E 的虫洞,走过这条虫洞,可以回到 T 秒之间。
输出格式
输出共 F 行,每行输出一个结果。如果约翰能够在出发时刻之前回到出发地,则输出 YES,否则输出 NO。
数据范围
1 ≤ F ≤ 5
1 ≤ N ≤ 500,
1 ≤ M ≤ 2500,
1 ≤ W ≤ 200,
1 ≤ T ≤ 10000,
1 ≤ S,E ≤ N
输入样例:
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
输出样例:
NO
YES
来源:https://www.acwing.com/problem/content/description/906/
2. 思路分析:
3. 代码如下:
import collections from typing import List class Solution: def spfa(self, n: int, g: List[List[int]]): q = collections.deque() vis = [0] * (n + 1) # count记录到某个点的最短路径的边数 count = [0] * (n + 1) # dis初始化为任意值都可以, 因为存在负环所以到某个点的最短路径长度一定大于等于n dis = [0] * (n + 1) for i in range(1, n + 1): # 将所有点入队 q.append(i) vis[i] = 1 while q: t = q.popleft() vis[t] = 0 for next in g[t]: if dis[next[0]] > dis[t] + next[1]: dis[next[0]] = dis[t] + next[1] count[next[0]] = count[t] + 1 if count[next[0]] >= n: return True if vis[next[0]] == 0: q.append(next[0]) vis[next[0]] = 1 return False def process(self): # T组测试数据 T = int(input()) while T > 0: n, m1, m2 = map(int, input().split()) g = [list() for i in range(n + 1)] for i in range(m1): # 这里m1是无向边 a, b, c = map(int, input().split()) g[a].append((b, c)) g[b].append((a, c)) # 虫洞属于负数边 for i in range(m2): a, b, c = map(int, input().split()) g[a].append((b, -c)) # 存在负环 if self.spfa(n, g): print("YES") else: print("NO") T -= 1 if __name__ == "__main__": Solution().process()
这篇关于904 虫洞(spfa找负环)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)