[백준][Python] 1865 웜홀

시작정점을 어디로 두어야 하는가?

초기 최단거리값을 float('inf)가 아닌 정수로 두어야 하는 이유가 무엇인가?

두가지에 대해 고민해볼 필요가 있는 문제

두 가지 조건에 따라 시작 지점에서 도달 할 수 있는 또는 도달할 수 없는 음수 사이클 판별 가부가 결정된다.

 

import sys
input = sys.stdin.readline

def bellman_ford(start):
    dists[start] = 0
    for cycle in range(n):
        for cur_node, next_node, cost in edges:
            if dists[cur_node] + cost < dists[next_node]:
                dists[next_node] = dists[cur_node] + cost
                if cycle == n - 1:
                    return True
    return False

INF = 123456789
for test in range(int(input())):
    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))

    dists = {i: INF for i in range(1, n + 1)}
    
    print("YES" if bellman_ford(1) else "NO")