[알고리즘][Python] 백준 1865 웜홀 문제 풀이

문제 출처 : www.acmicpc.net/problem/1865

1865번: 웜홀

---

문제 해석 : 웜홀은 시간이 거꾸로 흐른다. 이때 일반 경로와 웜홀을 통해서 자신이 출발했던 정점을 그 이전의 시간으로 돌아오는 것이 가능한지 구하는 문제이다.

 

문제 풀이 :  벨만-포드 알고리즘을 통해서 풀이가능하다.

: 모든 정점에 대해서 자신의 정점까지의 거리가 적은 것으로 갱신되는 것을 N번 반복한다.

: 이때 계속해서 반복된다면 이는 왕복할때마다 가중치가 줄어드는 곳이 있다는 뜻이고 정답을 알 수 있다.

---

풀이 코드

import sys
INF = int(100000)
input = sys.stdin.readline


def solution(N, distance, graph):
    distance[1] = 0
    for check in range(N):
        for vertex in range(1, N+1):
            for next_vertex, next_cost in graph[vertex]:
                if distance[next_vertex] > distance[vertex] + next_cost:
                    distance[next_vertex] = distance[vertex] + next_cost
                    if check == N-1:
                        return False
    return True


TC = int(input())
for test_case in range(TC):
    N, M, W = map(int, input().split())

    graph = [[] for _ in range(N+1)]
    distance = [INF] * (N+1)

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

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

    if solution(N, distance, graph):
        print("NO")
    else:
        print("YES")

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.