웜홀

• 시작점을 포함하는 음수 사이클의 존재 여부를 묻는 문제이다. 그런데 시작점이 딱히 정해진 것이 아니므로, 그냥 그래프 안에 음수 사이클이 존재하는지를 찾으면 된다. 음수 사이클의 존재 여부는 Shortest Path Faster Algorithm (SPFA)로 찾을수 있다.
• 주의할 점은, 시작점을 임의로 지정해주고서 SPFA를 돌린다면, 시작점에서 도달 불가능한 점들로 이루어진 사이클은 찾을수 없다. 따라서, 임의의 시작점에서 SPFA를 돌린 다음 음수 사이클이 없다면, 도달 불가능했던 점들 중에서 시작점을 다시 잡고 SPFA를 돌리고, 이걸 반복해서 풀어야 한다.
• 하지만 좀더 간단한 구현 방법은 SPFA를 시작할때 모든 점이 큐에 들어가 있는 상태로 초기화 한 후에 SPFA를 돌리는 것이다. teflib.tgraph.spfa를 가져다 쓸때는 이렇게 할수 없으므로, 대신 그래프에 가상 노드를 하나 추가한 뒤에, 그 노드로부터 모든 다른 노드로 향하는 가중치가 0인 엣지 N개를 추가해준다. 그리고 그 가상노드를 시작점으로 삼아서 SPFA를 돌리면 똑같은 효과를 얻을수 있다.
• 시간복잡도는 O(VE)

"""Solution code for "BOJ 1865. 웜홀".

- Problem link: https://www.acmicpc.net/problem/1865
- Solution link: http://www.teferi.net/ps/problems/boj/1865

Tags: [SPFA]
"""

import sys
from teflib import tgraph

INF = float('inf')


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N, M, W = [int(x) for x in sys.stdin.readline().split()]
        wgraph = [{} for _ in range(N + 1)]
        wgraph[N] = {u: 0 for u in range(N)}
        for _ in range(M):
            S, E, T = [int(x) for x in sys.stdin.readline().split()]
            try:
                min_weight = wgraph[S - 1][E - 1]
                wgraph[S - 1][E - 1] = wgraph[E - 1][S - 1] = min(min_weight, T)
            except KeyError:
                wgraph[S - 1][E - 1] = wgraph[E - 1][S - 1] = T
        for _ in range(W):
            S, E, T = [int(x) for x in sys.stdin.readline().split()]
            try:
                min_weight = wgraph[S - 1][E - 1]
                wgraph[S - 1][E - 1] = min(min_weight, -T)
            except KeyError:
                wgraph[S - 1][E - 1] = -T

        dists = tgraph.spfa(wgraph, N)
        print('YES' if -INF in dists else 'NO')


if __name__ == '__main__':
    main()

• Dependency: teflib.tgraph.spfa