[BAEKJOON]1865 웜홀 - Python

문제 요약

• 알고리즘 분류: 트리
• 난이도: Gold3
• 문제내용:
  • 도로는 방향이 없고 웜홀은 방향이 있다.
  • 웜홀로 이동하면 시간은 거꾸로 흘러 간다.
  • 자기 자신으로 돌아 올때 거꾸로 흘러 가는지 출력해라.
• 사이트: https://www.acmicpc.net/problem/1865

1865번: 웜홀

문제풀이

   이번에는 문제 유형은 벨만-포드 알고리즘이다. 벨만-포드 알고리즘에 대한 자세한 설명은 여기에서 보면된다.

 기본적으로 벨만-포드 알고리즘 지식과 구현 하면되기 때문에 자세한 설명은 생략한다. 다만 주위해야할점은 간선이 다리는 방향이 없어서 S → E, E → S 둘다 포함 시켜야 하고 거리를 선언할때 시작점을 초기화 없이 진행 하면된다.

 

Code

Python

 여기서 INF 설정할때 무한(float('inf'))으로 하면  거리를 비교 할수가 없다.

import sys
input = sys.stdin.readline
INF = 1e9

def Bellman_Ford():
    distances = [INF] * (N + 1)
    
    # 라운드 마다 진행
    for i in range(N):
        # 각 간선
        for j in range(len(edges)):
            current_node, next_node, cost = edges[j]
            
            if distances[next_node] > distances[current_node] + cost:
                distances[next_node] = distances[current_node] + cost
                # n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
                if i == N - 1: return True
    
    return False
                
        
for _ in range(int(input())):
    N, M, W = map(int, input().split())
    edges = []
    for _ in range(M):
        S, E, T = 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))
    
    print('YES' if Bellman_Ford() else 'NO')