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 Listclass Solution:def spfa(self, n: int, g: List[List[int]]):q = collections.deque()vis = [0] * (n + 1)# count记录到某个点的最短路径的边数count = [0] * (n + 1)# dis初始化为任意值都可以, 因为存在负环所以到某个点的最短路径长度一定大于等于ndis = [0] * (n + 1)for i in range(1, n + 1):# 将所有点入队q.append(i)vis[i] = 1while q:t = q.popleft()vis[t] = 0for next in g[t]:if dis[next[0]] > dis[t] + next[1]:dis[next[0]] = dis[t] + next[1]count[next[0]] = count[t] + 1if count[next[0]] >= n: return Trueif vis[next[0]] == 0:q.append(next[0])vis[next[0]] = 1return Falsedef 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 -= 1if __name__ == "__main__":Solution().process()