[백준] 1865번 : 웜홀

1865번: 웜홀

1865번: 웜홀

🤔 문제분석

밸만포드로 문제를 해결할 수 있습니다. 어떠한 노드에서 출발해도 상관이 없기때문에 1번 노드에서 출발 하여 문제를 해결하였습니다.

💻 코드

import sys
input = sys.stdin.readline

TC = int(input())

def bellman_ford(start):
    distance = [INF for _ in range(N+1)]
    distance[start] = 0
    for n in range(N):
        for e in range(M*2 + W):
            start, end, cost = edge[e][0], edge[e][1], edge[e][2]
            new_cost = distance[start] + cost
            if distance[end] > new_cost:
                distance[end] = new_cost
                
                if n == N-1:
                    return True
                
    return False
    
for _ in range(TC):
    N, M, W = map(int, input().split())
    
    edge = []
    INF = sys.maxsize
    
    for _ in range(M):
        S, E, T = map(int, input().split())
        edge.append((S, E, T))
        edge.append((E, S, T))
        
    for _ in range(W):
        S, E, T = map(int, input().split())
        edge.append((S, E, -T))
        
    if bellman_ford(1):
        print("YES")
    else:
        print("NO")

🎯 피드백 및 개선사항

기존 벨만포트와 다른것은 distance[start] ≠ INF 일때만 방문했었는데, 그렇지 않아도 됩니다. 왜냐하면 연결되어있지 않는 간선이 존재할 수 있을 뿐더러, 우리가 구하고자하는것은 음의간선으로 무한 사이클이 있는지 판별하는거에 관심이 있기 때문입니다.