99클럽 코테 스터디 4일차 TIL + Bellman-Ford

• 문제: Baekjoon1865: 웜홀
  • 설명: 그래프가 주어질 때 음수 사이클이 있는지 판별하여라.
• 풀이
  • 어떤 노드에서 출발해서 다시 자기자신으로 돌아왔을 때 든 시간이 더 줄어드는 경우를 찾는 문제이므로 Bellman-Ford 알고리즘을 사용하여 음수 사이클을 판별한다.
  • 시작점은 중요하지 않을 뿐더러 시작점이 모든 점이다. 따라서 1번 노드의 최단 거리를 0으로 두지 않도록 주의한다.
    • 물론 두어도 풀리기는 한다.
• 오늘의 회고
  • 오늘 틀렸던 부분은 초기에 각 노드들의 최단 거리를 float("inf")로 초기화했던 점이다.
    • 아래와 같은 입력이 있다고 가정해보자.

      3 1 1 # 노드 3개, 도로 1개, 웜홀 1개
      2 3 1 # 2 <-> 3 인 도로의 가중치가 1
      3 2 2 # 3 -> 2 인 도로의 가중치가 -2

    • 노드는 1, 2, 3 3개가 있지만 1번 노드는 어떤 노드와도 연결되어 있지 않다.
    • 이때 2번 3번 노드는 음수 사이클이 있지만,
    • 3번 노드에서 2번 노드를 웜홀을 통해서 갈 때 inf - 2와 inf를 비교하게 되고,
    • 이는 같기 때문에 갱신이 되지 않는다.
      • python의 inf는 의미 그대로 무한이기에 무한에서 특정 값을 빼도 무한이다. 따라서 같다.
    • 최종적으로 음수 사이클 판별 간 갱신이 되지 않으므로 판별되지 않을 것이다.
    • float("inf") 대신 이를 적절히 큰값($1,000,000,007$)으로 두어서 갱신이 되도록 하여 문제를 해결하였다.
      • 이는 무한이 아니기 때문에 특정 값을 빼면 무조건 뺀 값이 작도록 설정하였다.
      • $10^9+7$을 고른 이유는 딱히 없다 적당히 나올 수 있는 최단 경로의 최댓값보다 크면 된다.
      • 가령 0x3f3f3f3f라든지, $10^9$ 라든지...

Code

# Baekjoon01865.py
import sys
input = sys.stdin.readline

INF = 1_000_000_007

def solve():
    n, m, w = map(int, input().split())

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

        edges.append((s, e, t))
        edges.append((e, s, t))

    for _ in range(w):
        s, e, t = map(int, input().split())

        edges.append((s, e, -t))

    distance = [INF for _ in range(n + 1)]

    for _ in range(n - 1):
        for s, e, t in edges:
            distance[e] = min(distance[e], distance[s] + t)

    negative = False
    for s, e, t in edges:
        if distance[e] > distance[s] + t:
            negative = True
            break

    print("YES" if negative else "NO")


for _ in range(int(input())):
    solve()