1865 웜홀 - 최단 거리(벨만포드)

문제에서 두 지점을 연결하는 도로가 한 개보다 많을 수도 있다고 한다. 또한 지금까지 문제는 다시 돌아갈 필요가 없었는데 - 특정 노드에서 다른 노드까지의 경로는 다시 돌아가는 경우가 없음 - 이 문제에서는 웜홀을 들렀다가 다시 출발 지점으로 돌아가는 문제이므로 인접리스트를 만들때 단방향이 아니라 양방향으로 입력한다.

adjList[S].append((E,cost))
adjList[E].append((S,cost))

웜홀에서 다른 노드로 이동하는 비용을 음수로 저장하고 벨만포드를 하면 된다. 하지만 출발노드가 정해져 있지 않아 모든 노드에 대해서 벨만포드를 수행하면 되나 싶었는데 그냥 음수 순환이 존재하는지만 확인하면 되서 아무 노드에서나 출발을 하면 되는 문제였다.

따라서, 최단 경로를 기록할 리스트의 1번 인덱스에 0으로 초기화할 필요가 없으며, 벨만 포드 알고리즘에서 현재 노드의 값이 INF(무한대)인지 아닌지 확인하는 조건을 넣으면 안된다.

import sys
input = sys.stdin.readline
 
 
def bellmanFord():
    global isPossible
 
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for wei, vec in adjList[j]:
                if dist[vec] > wei + dist[j]:
                    dist[vec] = wei + dist[j]
                    if i == N:
                        isPossible = False
                    
 
T = int(input())
 
for _ in range(T):
    N, M, W = map(int, input().split())
 
    INF = 2147483647
    dist = [INF for _ in range(N + 1)]
 
    adjList = [[] for _ in range(N + 1)]
 
    for _ in range(M):
        S, E, T = map(int, input().split())
 
        adjList[S].append((T, E))
        adjList[E].append((T, S))
    
    for _ in range(W):
        S, E, T = map(int, input().split())
 
        adjList[S].append((-T, E))
    
    isPossible = True
    
    bellmanFord()
 
    print("NO" if isPossible else "YES")