[BOJ] Q1865 웜홀

[BOJ] Q1865 웜홀

Question

Language: Python

Difficulty: Gold 3

일반 도로를 이용할 때는 시간이 앞으로 가고, 웜홀을 이용하게 되면 시간이 뒤로 간다. 이럴때, 출발지에서 시작하여 다시 출발지로 돌아왔을 때 시간이 뒤로 가 있을 경우가 존재하는 지를 묻는 문제이다.

해당 문제는 음수 사이클이 있는지 없는지 여부를 판단하기만 하면 되는 간단한 문제이다.

Solution

from math import inf

def solution(edges,N):
    distance=[10001] * (N+1)
    distance[1]=0
    
    for i in range(N):
        for v1,v2,weight in edges:
            cost=distance[v1]+weight
            if distance[v2]>cost:
                distance[v2]=cost
                if i==N-1:
                    return True
    return False

if __name__ == "__main__":
    testcases=int(input())
    for _ in range(testcases):
        N,e,wormhalls=map(int,input().split())
        edges=[]
    
        for _ in range(e):
            start,end,weight=map(int,input().split())
            edges.append([start,end,weight])
            edges.append([end,start,weight])
            
        for _ in range(wormhalls):
            start,end,weight=map(int,input().split())
            edges.append([start,end,-weight])
            
        if solution(edges,N):
            print("YES")
        else: 
            print("NO")