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()