백준(1865) - 웜홀 Python

백준(1865) - 웜홀

문제풀이: Bellman Ford 알고리즘, 파이썬

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

testcase = int(input())

def bellman():
    for i in range(1, n+1):
        for j in range(1, n+1):
            for now, cost in graph[j]:
                if distance[now] > cost + distance[j]:
                    distance[now] = cost + distance[j]
                    if i == n:
                        return False
    return True


for _ in range(testcase):
    n, m, w = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    distance = [INF] * (n+1)

    for i in range(m):
        start, end, time = map(int, input().split())
        graph[start].append((end, time))
        graph[end].append((start, time))

    for i in range(w):
        start, end, time = map(int, input().split())
        graph[end].append((start, -time))

    answer = bellman()
    print("NO" if answer else "YES")