소스 코드

import sys
input = sys.stdin.readline

for _ in range(int(input().rstrip())):
    N, M, W = map(int, input().rstrip().split())
    edges = []

    for _ in range(M):
        S, E, T = map(int, input().rstrip().split())
        edges.append((S, E, T))
        edges.append((E, S, T))
    
    for _ in range(W):
        S, E, T = map(int, input().rstrip().split())
        edges.append((S, E, -T))

    # 최단 거리는 필요 없고 오직 음의 사이클이 있는지만 판단하면 되기 때문에,
    # costs는 임의의 값으로 모두 똑같이만 채워두면 된다.
    costs = [0] * (N + 1)
    result = False
    for step in range(N):
        for start, end, cost in edges:
            cal_cost = costs[start] + cost

            if cal_cost < costs[end]:
                costs[end] = cal_cost

                if step == N - 1:
                    result = True
    
    print("YES" if result else "NO")

풀이 요약

1. 문제에서 출발점에서 떠나서 다시 출발점으로 돌아왔을 때, 그 비용이 음수인 경우가 존재하는가 라는 질문은, 그래프에서 음의 사이클이 하나라도 존재하는가 라는 질문과 같다. 즉 벨만-포드 알고리즘을 활용하여 음의 사이클을 찾아주자.

2. 그런데 해당 질문에 대한 답을 구하기 위해선, 최단 거리 정보들은 전혀 필요가 없고, 그저 음의 사이클 존재 여부만 알면 되기 때문에, 출발 노드를 따로 지정하여 그 인덱스의 비용만 0으로 초기화한다거나, 다른 인덱스는 -sys.maxsize로 초기화해둔다거나 할 필요가 없다. 그저 비용 리스트를 모두 동일한 값으로만 초기화해둔다면, 음의 사이클을 찾아낼 수 있다.

어려웠던 점, 배운 점

• 문제에서 말하는 출발점에서 떠나서 다시 출발점으로 돌아왔을 때, 그 비용이 음수인 경우가 존재하는가 라는 질문이 음의 사이클이 존재하냐와 같다는 말인걸 깨닫지 못하고 계속 헤맸다. 어찌 저찌 복잡한 풀이로 가능한 풀이를 구현해냈지만 TLE가 났다.

  해당 풀이도 시간복잡도를 생각해보니 O(V^2 * E) 라서 충분히 TLE가 날만한 시간복잡도였다. 이걸 먼저 계산해보고 했어야했는데..

  암튼 그렇게 삽질하다가 결국 다른 사람 풀이를 참고해서 풀 수 있었다. 특히 음의 사이클 존재 여부를 알아내기 위해서 비용 리스트를 동일한 값으로만 전부 초기화주면 되는 점이 인상적이었다.