[백준/파이썬] 1865번

📍백준 1865 문제

https://www.acmicpc.net/problem/1865

코드

import sys
input = sys.stdin.readline


def bf(start):
    dist = [int(1e9)] * (n+1)
    dist[start] = 0
    for i in range(n):
        for s, e, t in road:
            distance = dist[s] + t
            if distance < dist[e]:
                dist[e] = distance
                if i == n-1:
                    return True
    return False


testCase = int(input())
for _ in range(testCase):
    # n: 지점, m: 도로, w: 웜홀 개수
    n, m, w = map(int, input().split())
    road = []
    for _ in range(m):
        s, e, t = map(int, input().split())
        road.append((s, e, t))
        road.append((e, s, t))

    for _ in range(w):
        s, e, t = map(int, input().split())
        road.append((s, e, -t))
    isCycle = bf(1)
    if isCycle:
        print("YES")
    else:
        print("NO")

풀이

벨만-포드 알고리즘을 이용하면 된다.