[백준] 웜홀

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

1865번: 웜홀

음의 가중치가 있는 그래프에서 음의 사이클이 있는지 여부를 체크하는 문제입니다. 벨만포드의 개선버전인 SPFA 알고리즘을 활용하여 풀이하였습니다. 분리되어 있는 그래프가 있을 수 있어서 Visited 배열을 통하여 방문되지 않은 그래프가 있으면 해당 그래프에서 음의 사이클이 있는지를 체크해주도록 하였습니다. 

 

최단경로와 관련된 알고리즘들이 많습니다. 다익스트라, 벨만포드, 플로이드와샬, SPFA까지 추후에 한번에 정리해보도록 하겠습니다.

 

import sys
from collections import defaultdict, deque

sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

T = int(input())

n, m, w = -1, -1, -1
graph = None
visited = None


def spfa(start):
    in_q = [False] * (n + 1)
    dist = [sys.maxsize] * (n + 1)
    cycle = [0] * (n + 1)

    q = deque([start])
    dist[start] = 0
    in_q[start] = True

    cycle[start] += 1
    visited[start] = True

    while q:
        cur = q.popleft()

        in_q[cur] = False

        for next, nt in graph[cur]:
            next_cost = nt + dist[cur]
            visited[next] = True

            if next_cost < dist[next]:
                dist[next] = next_cost

                if not in_q[next]:
                    cycle[next] += 1

                    if cycle[next] == n:
                        return False

                in_q[next] = True
                q.append(next)

    return True


for t in range(T):
    n, m, w = tuple(map(int, input().split()))
    graph = defaultdict(list)

    for _ in range(m):
        s, e, t = tuple(map(int, input().split()))
        graph[s].append((e, t))
        graph[e].append((s, t))

    for _ in range(w):
        s, e, t = tuple(map(int, input().split()))
        graph[s].append((e, -t))

    flag = False
    visited = [False] * (n + 1)
    for i in range(1, n + 1):
        if not visited[i]:
            ret = spfa(i)

            if not ret:
                print('YES')
                flag = True
                break

    if not flag:
        print('NO')