[백준] 1865번 - 웜홀 (파이썬)

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

# 웜홀
import sys
input = sys.stdin.readline
MAX = sys.maxsize


def bf():
    for k in range(1, N+1):
        for i in range(1, N+1):
            for time, city in arr[i]:
                if times[city] > time + times[i]:
                    times[city] = time + times[i]
                    if k == N:
                        return True
    return False


T = int(input())
for _ in range(T):
    N, M, W = map(int, input().split())
    arr = [[]for _ in range(N+1)]
    for _ in range(M):
        a, b, time = map(int, input().split())
        arr[a].append((time, b))
        arr[b].append((time, a))
    for _ in range(W):
        a, b, time = map(int, input().split())
        arr[a].append((-time, b))

    times = [MAX] * (N+1)
    if bf():
        print('YES')
    else:
        print('NO')

 

최단거리, 벨만포드

1. 테스트 케이스 만큼

2. 인접 리스트로 입력을 받고

3. 벨만 포드

    - 단지 음수의 순환만 확인하면 되는 것이라서 시작을 따로 입력하지 않고 총 걸리는 시간의 변화만 주시

    - 마지막 N번째 반복에서도 값이 변하면 음수의 순환이 존재한다는 뜻

4. 음수의 순환이 있으면 YES, 없으면 NO