[백준 1865번] 웜홀 - python

문제 링크

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

1865번: 웜홀

풀이

 - 벨만 포드 문제 

문제의 뜻을 웜홀을 거쳤을 때 최단 거리가 줄어들 수 있는지 물어보는 줄 알았는데,

음수 사이클이 존재하는지 물어보는 문제였다. 

이 때, 어느 지점에서 출발하는지에 관계없이 음수 사이클이 존재하는지만 판단하면 되므로

dist[node] != INF 조건을 삭제해주어야 한다. 

dist[node] != INF 는 dist[start] = 0으로 설정한 시작 지점에서부터 이어진 노드의 최소 거리를 구하기 위한 조건이기 때문에

삭제 시 시작 지점과 관계없이 진행되어 dist는 시작 지점으로부터 최단 거리를 저장하는 것이 아니라,

음수 싸이클이 존재하는지 판단할 수 있게 된다. 

- 처음에는 모든 시작점에서부터 벨만 포드 알고리즘을 실행하고 음수 사이클이 있는지 판단하여 시간초과 발생 

# https://www.acmicpc.net/problem/1865
import sys
input = sys.stdin.readline 

def bf(start):
    dist = [INF] * (n+1)
    # 자기 자신까지의 거리 0 으로 초기화
    dist[start] = 0 
    for i in range(n):
        # 매 반복마다 모든 간선 확인 
        for edge in edges:
            # 현재 노드 
            node = edge[0]
            # 다음 노드 
            next_node = edge[1]
            # 가중치
            cost = edge[2]
            # 현재 노드를 거쳐 다른 노드로 이동하는 거리가 더 짧을 경우 
            if dist[next_node] > dist[node] + cost:
                # 갱신
                dist[next_node] = dist[node] + cost
                # n-1 번 이후 반복에도 값이 갱신된다면 음수 순환 존재 
                if i == n-1:
                    return True
    return False 
    
test = int(input())
INF = int(1e9)
for _ in range(test):
    n, m, w = map(int,input().split())
    
    edges = []

    for _ in range(m):
        a, b, c = map(int,input().split())
        edges.append((a,b,c))
        edges.append((b,a,c))
        
    for _ in range(w):
        a, b, c = map(int,input().split())
        edges.append((a,b,-c))
    # 시작 지점은 상관없음 
    cycle = bf(1)
    # 음수 사이클이 존재하면 
    if cycle:
        print('YES')
    else:
        print('NO')