[BOJ 1865] 웜홀(Python)

문제

웜홀

문제 해설

벨만-포드를 이용하여 음수 사이클의 존재 여부를 판단하는 문제입니다.

원래의 벨만-포드 알고리즘은 시작하는 노드에서 도달할 수 없는 노드를 inf값을 주어 판단했습니다. 하지만 이 문제에서는 시작 노드가 정해져 있지 않기 때문에 서로 연결되어 있지 않은 그래프에 대해서는 갱신을 할 수가 없습니다. 갱신이 불가하기 때문에 다른 그래프에 음수 사이클이 생기는지 판단을 할 수 없습니다.

그러므로 초기 dist의 모든 값들을 아무 값으로 초기화 한 뒤, 벨만-포드와 마찬가지로 진행을 하되, inf면 갱신을 하지 않았던 부분을 삭제해주시면 됩니다. if dist[a] != inf 이 코드는 어디서 어디까지 최단 거리는 구할 수 없지만 음수 사이클에 대한 판정은 할 수 있습니다.

풀이 코드

import sys

input = sys.stdin.readline

def bf():
    for i in range(n):
        for a, b, c in edges:
        # if dist[a] != inf and if idst[b] > dist[a] + c
            # -> if dist[b] > dist[a] + c
            if dist[b] > dist[a] + c:
                # 음수 사이클 발생
                if i == n - 1:
                    return True
                dist[b] = dist[a] + c
    return False


for _ in range(int(input())):
    n, m, w = map(int, input().split())
    edges = []
    dist = [0] * (n + 1)
    # 도로 입력
    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))
    print("YES") if bf() else print("NO")