[BOJ] 1865 - 웜홀 (Python)

 

 

아이디어

 

벨만-포드로 음의 사이클이 존재하는지 확인한다.

 

 

풀이

 

도로는 방향이 없고 웜홀은 방향이 있음에 주의해야 한다.

 

import sys

input = sys.stdin.readline

INF = int(1e11)

def solution():
    TC = int(input())
    for _ in range(TC):
        N, M, W = map(int, input().split())
        graph = [dict() for _ in range(N+1)]
        for _ in range(M):
            S, E, T = map(int, input().split())
            graph[S][E] = min(graph[S].get(E, INF), T)
            graph[E][S] = min(graph[E].get(S, INF), T)
        for _ in range(W):
            S, E, T = map(int, input().split())
            graph[S][E] = min(graph[S].get(E, INF), -T)
        D = [INF]*(N+1)
        for _ in range(N-1):
            for i in range(1, N+1):
                for j, t in graph[i].items():
                    if D[i]+t < D[j]:
                        D[j] = D[i]+t
        _D = D[:]
        for i in range(1, N+1):
            for j, t in graph[i].items():
                if _D[i]+t < _D[j]:
                    _D[j] = _D[i]+t
        print('NO' if D == _D else 'YES')

solution()