백준 1865 웜홀

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

 

 이 문제는 양방향 도로와 단방향 웜홀(시간이 뒤로감) 이 주어지고 이 때 음의 사이클이 존재하는지 물어보는 문제이다. 음의 사이클이 있는지를 알아내려면 벨만-포드 알고리즘을 쓰는 것이 제격이다. 

 

 벨만 - 포드 알고리즘은 그래프의 노드의 개수만큼 반복하며, 다익스트라 알고리즘처럼 경유하는 경우가 더 짧을 경우 계속해서 갱신하는 방식이다. 얼핏보면 쓸데 없는 계산을 더하는 것처럼 보이지만, 이 알고리즘의 장점은 이미 그래프의 노드의 개수만큼 반복하여 최적의 거리를 구했다고 생각했을때, 한번 더 돌려서 이때 최적경로가 갱신된다면, 음의 사이클이 생긴 것이라는 것을 알아챌 수 있단 점이다. 

 

 필자는 본디 처음엔 거리 리스트를 math.inf로 했으나 이리하면 실수형과 정수형의 계산에서 오차가 생기므로 그냥 적당히 큰 수를 무한대로 하였다.

import sys
input = sys.stdin.readline
INF=int(100000)

def Bellman(N,graph,d):
    d[1]=0

    for check in range(N):
        for now_node in range(1,N+1):
            for next_node,time in graph[now_node]:
                if d[next_node] > d[now_node] + time:
                    d[next_node] = d[now_node]+time
                    if check == N-1:
                        return False
    
    return True

TS = int(input())
for _ in range(TS):
    N,M,W = map(int,input().split())
    graph=[[] for _ in range(N+1)]
    d = [INF]*(N+1)
    for _ in range(M):
        S,E,T = map(int,input().split())
        graph[S].append([E,T])
        graph[E].append([S,T])
    
    for _ in range(W):
        S,E,T = map(int,input().split())
        graph[S].append([E,-T])
    
    if Bellman(N,graph,d):
        print('NO')
    else:
        print('YES')