[백준] 1865번: 웜홀

문제

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

풀이

벨만포드 알고리즘을 활용한 풀이
음수 가중치가 있기 때문에 벨만 포드 알고리즘을 사용했다.

      if distances[end] > distances[mid] + weight:

이 문제는 음수 가중치 사이클이 있다면 Yes, 없다면 No 를 반환하는 문제이다.
거리는 계산하지 않아도 된다.

따라서 위 분기문에서 distances[mid] != INF 을 빼서
한 벨만포드 루틴에서 바로 음수 가중치 사이클이 있는지 없는지 판단하여
답을 도출해 냈다.

import sys

INF = sys.maxsize
T = int(input())

def bellmanFord(start, graph, N):
    distances = [INF] * (N + 1)
    distances[start] = 0

    for _ in range(N - 1):
        for mid, end, weight in graph:
            if distances[end] > distances[mid] + weight:
                distances[end] = distances[mid] + weight

    for mid, end, weight in graph:
        if distances[end] > distances[mid] + weight:
            return "YES"
    return "NO"

def solution(T):
    for _ in range(T):
        N, M, W = map(int, input().rstrip().split(" "))
        graph = []
        for _ in range(M):
            start, end, weight = map(int, input().rstrip().split(" "))
            graph.append((start, end, weight))
            graph.append((end, start, weight))
        for _ in range(W):
            start, end, weight = map(int, input().rstrip().split(" "))
            graph.append((start, end, -weight))

        print(bellmanFord(1, graph, N))

solution(T)