백준 1865. 웜홀

https://www.acmicpc.net/problem/1865

import sys
input = sys.stdin.readline
INF = int(1e9)

def bf(start): # 벨만-포드 알고리즘
    dist[start] = 0 # 시작 노드의 거리는 0
    for i in range(1, n+1): # 각 노드의 최단 경로를 최대 (노드 개수 - 1)번까지 반복해서 계산
        for s in range(1, n+1): # 모든 간선들을 검사해서 최소 거리로 갱신
            for next, time in arr[s]:
                if dist[next] > dist[s] + time:
                    dist[next] = dist[s] + time # 더 작은 거리로 갱신 가능한 경우 최단 거리 배열을 갱신
                    if i == n: # n번 이후에도 값이 갱신되면 음수 사이클 존재(n-1번 반복 후에 최단 경로 완성=갱신x)
                               # 두 노드의 최단 경로는 최대로 n-1개의 간선만으로 구성되기 때문!
                        return True
    return False

tc = int(input())
for _ in range(tc):
    n, m, w = map(int,input().split()) # 지점, 도로, 웜홀의 개수
    arr = [[] * (n+1)]
    dist = [INF] * (n+1)

    for _ in range(m): # 도로(방향없음)
        start, end, time = map(int,input().split())
        arr[start].append((end,time))
        arr[end].append((start,time))

    for _ in range(w): # 웜홀(방향있음)
        start, end, time = map(int, input().split())
        arr[start].append((end,-time))

    # 음수 싸이클이 있는지 유무 판단
    negative_cycle = bf(1)
    if not negative_cycle:
        print("NO")
    else:
        print("YES")