[백준] 1865 웜홀

---

그래프에 음의 사이클이 존재하는 지를 판단하는 문제이다.

 

음의 사이클을 발견할 수 있는 알고리즘은 플로이드-와샬, 벨만-포드, SPFA 알고리즘 세 가지가 있다. 시작점이 정해지지 않아 모든 시작점에 대해서 SPFA 알고리즘을 사용하여 해결했다. 

 

하지만 시간이 너무 오래걸려 다른 풀이를 살펴보니 시작점을 특정하고 벨만-포드 알고리즘을 사용하면 해결되었다. 이에 대해서 명확한 글은 없었지만, 무향 그래프이고 단순히 음의 사이클 여부만 판단하면 되기 때문에 벨만-포드 알고리즘을 사용한 것 같다.

 

한 가지 의문은 특정 시작점에 대해서 SPFA는 해결되지 않는다는 것인데 이는 시간을 가지고 알아봐야 할 것 같다.

from sys import stdin

readline = stdin.readline
INF = 10000 * 500 + 1


def is_possible():
    dist = [INF] * N
    dist[0] = 0
    updated = False
    for i in range(N):
        updated = False
        for j in range(N):
            for v, t in graph[j]:
                if dist[v] > dist[j] + t:
                    dist[v] = dist[j] + t
                    updated = True
        if not updated:
            break

    return updated

if __name__ == "__main__":
    T = int(readline().strip())
    for _ in range(T):
        N, M, W = map(int, readline().split())
        graph = [[] for _ in range(N)]

        for _ in range(M):
            S, E, T = map(int, readline().split())
            graph[S-1].append([E-1, T])
            graph[E-1].append([S-1, T])

        for _ in range(W):
            S, E, T = map(int, readline().split())
            graph[S-1].append([E-1, -T])

        if is_possible():
            print('YES')
        else:
            print('NO')