[Python] 백준 1865번 - 웜홀

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

1865번: 웜홀

타임머신 문제와 비슷한 유형이다.

다른 점이라면 bf 함수에서 세번째 for문 안에 있는 if문을 돌릴 때, 

 

타임머신에서는 아래의 if문을 사용하여 시작점과 연결된 경로가 있는지 확인해야 했고,

 if dist[a] != float('inf') and dist[next] > dist[a] + time:

 

웜홀 문제에서는 시작점이 주어지지 않으므로 이에 대한 확인 없이 negative cycle 여부만 체크하면 된다는 것이다.

따라서 웜홀 문제에서 if문은 아래처럼 작성하였다.

 if dist[next] > dist[s] + time:

 

 

정답 코드와 같았는데 어느 한 테스트케이스에서 자꾸 에러가 났다.

나는 dist를 초기화할 때 

 dist = [float('inf') for _ in range(n+1)]

float('inf')로 무한대값을 넣어주었는데

 

정답 코드에서는 dist의 초깃값을 임의의 무한대 값으로 설정해주었다.

이 부분 빼고는 다 같아서 float('inf')를 10001 이라는 값으로 수정하였다.

( => 간선의 가중치인 T의 최댓값이 10000이므로 그것보다 1 큰 값으로 임의지정)

 dist = [10001 for _ in range(n+1)]

 

초깃값을 무한대로 하면 무한대 값에서 음수 가중치를 더해주어도 그대로 무한대이기 때문에

현재값과 그 전의 값이 비교가 되지 않아서 가중치 값이 갱신되지 않은 것이었다..!

어렵다 ! 벨만포드 !

 

 

 

#제출 코드 (PASS)

import sys
input = sys.stdin.readline

def bf(start):
    dist[start] = 0
    for i in range(1, n+1):
        for s in range(1, n+1):
            for next, time in graph[s]:
                if dist[next] > dist[s] + time:
                    dist[next] = dist[s] + time
                    if i == n: #n번 이후에도 값이 갱신되면 음수 사이클 존재.
                        return True
    return False

TC = int(input())
for i in range(TC):
    n, m, w = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    dist = [10001 for _ in range(n+1)]
    for j in range(m):
        s, e, t = map(int, input().split())
        graph[s].append([e, t])
        graph[e].append([s, t])
    for k in range(w):
        s, e, t = map(int, input().split())
        graph[s].append([e, -t])

    negative_cycle = bf(1)
    if not negative_cycle:
        print("NO")
    else:
        print("YES")