[백준 1865] 웜홀 - 골드3(벨만-포드 알고리즘)

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

1865번: 웜홀

문제

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

 

 

---

그래프와 관련된 문제이다.

시간 여행 이후 처음보다 시간이 되돌아가 있는 경우가 있는지 알아보아야 하는데, 이를 위해서 가장 빠른 길을 선택하며 이동해야 하므로 최단 거리 알고리즘을 사용한다.

그리고, 문제에서 주어지는 간선 중에는 음의 간선이 존재한다. 출발을 하였을 때보다 시간이 되돌아가 있는 경우는 그래프 내에 음의 간선으로 인한 싸이클이 형성되었을 때이다. 

따라서, 문제 해결을 위해 음의 간선의 순환 싸이클 존재 여부를 알 수 있는 벨만-포드(Bellman-Ford) 알고리즘을 선택하여 풀이했다.

 

이 문제에서 백준이가 출발하는 위치는 주어지지 않았으므로, 임의로 1에서 출발한다고 가정한다. 싸이클을 감지하면 'YES'를 출력, 감지하지 않았다면 'NO'를 출력한다.

 

 

<< 전체 코드 >>

import sys
input = sys.stdin.readline


def bellman_ford(start):
    dist = [int(1e9) for _ in range(n + 1)]
    dist[start] = 0
    
    for i in range(n):
        for cur, next_node, cost in edges:
            if dist[cur] + cost < dist[next_node]:
                dist[next_node] = dist[cur] + cost
                if i == n-1:
                    return True
    return False


tc = int(input())
for _ in range(tc):
    n, m, w = map(int, input().split())
    edges = []
    for _ in range(m):
        s, e, t = map(int, input().split())
        edges.append([s, e, t])
        edges.append([e, s, t])
    for _ in range(w):
        s, e, t = map(int, input().split())
        edges.append([s, e, -t])

    if bellman_ford(1):
        print('YES')
    else:
        print('NO')