[파이썬] 백준 1865 : 웜홀 (골드3)

[파이썬] 백준 1865 : 웜홀 (골드3)

• https://www.acmicpc.net/problem/웜홀

---

풀이

방향성 생각

• 음수 간선이 포함된 벨만 포드 문제.
• 그래프가 분리되어서 도달하지 못하는지, 아니면 현재 iteration에서 v가 짧아서 도달하지 못하는건지 확인을 해야한다.
• 음수 간선이 아닌 간선은 양방향, 음수 간선은 단방향 간선이다.
• 질문게시판에 에디토리얼(?)이 있으니 확인하면 좋은 문제.
• 그래프가 분리되어서 도달하지 못하는 것을 확인하기 위해, 더미 노드에ㅐ서 모든 노드로 간선을 이어주어서 문제를 풀이한다.
• visit 배열 업데이트 시, 이 노드가 유효한 노드인지(현재 iteration에서 도달 가능한지) 확인하고 진행한다.

 

---

파이썬

from collections import defaultdict as dd
import sys

input = lambda : sys.stdin.readline().strip()
INF = 1e9

TC = int(input())
for _ in range(TC):

    N,M,W = map(int,input().split())

    G = dd(lambda : INF)
    for n in range(1,N+1):
        G[(0,n)] = 0

    for _ in range(M):
        a,b,cost = map(int,input().split())
        G[(a,b)] = min(G[(a,b)],cost)
        G[(b,a)] = min(G[(b,a)],cost)

    for _ in range(W):
        a,b,cost = map(int,input().split())
        G[(a,b)] = min(G[(a,b)],-cost)


    def bf(sx):
        V = [INF]*(N+1)
        V[sx] = 0
        for n in range(N+1):
            for (a,b),cost in G.items():
                if V[a] != INF and V[a] + cost < V[b]:
                    V[b] = V[a] + cost
                    if n == N:
                        return True
        return False

    answer = bf(0)
    print('YES' if answer else 'NO')

---

코멘트

• 약간은 발상적?