1865.md

1865

Python

# bellman-ford Algorithm
import sys
input = sys.stdin.readline
INF = 10**9

def bf():
    for i in range(N):
        for now, nxt, time in edges:
            if dist[nxt] > dist[now] + time:
                dist[nxt] = dist[now] + time
                if i == N-1:
                    return True
    return False


def bf2():
    # N-1번(노드-1) 만큼 반복을 통해 최단 거리 갱신
    for _ in range(N-1):
        for now, nxt, time in edges:
            if dist[nxt] > dist[now] + time:
                dist[nxt] = dist[now] + time

    # 음수 사이클 확인
    for now, nxt, time in edges:
        if dist[nxt] > dist[now] + time:
            return True
    return False

TC = int(input())
for _ in range(TC):
    N, M, W = map(int, input().split())
    edges = []
    for _ in range(M):
        S, E, T = map(int, input().split())
        edges.append((S, E, T))
        edges.append((E, S, T))
    for _ in range(W):
        S, E, T = map(int, input().split())
        edges.append((S, E, -T))
    

    dist = [INF] * (N+1)
    negative_cycle = bf()
    if negative_cycle:
        print("YES")
    else:
        print("NO")