문제

문제 링크 : https://www.acmicpc.net/problem/1865

풀이

가중치가 음수인 간선이 있으므로 벨만-포드 알고리즘을 사용하면 된다.

다만, 벨만-포드 알고리즘의 구현부를 약간 수정해줘야 한다.

원래는 아래의 코드처럼 dist[s] != INF라는 조건이 들어가야 하지만, 이 문제에선 음수 사이클이 존재하는지만 확인하면 되니까 해당 조건이 들어가지 않아도 된다.

for i in range(n):
        for s,e,t in graph:
            if dist[s] != INF and dist[e] > dist[s] + t:
                if i == n - 1:
                    return True
                dist[e] = dist[s] + t

정답 코드

import sys
input = sys.stdin.readline
INF = int(1e9)

def bellman_ford(start,n):
    dist = [INF for i in range(n + 1)]
    dist[start] = 0
    for i in range(n):
        for s,e,t in graph:
            if dist[e] > dist[s] + t:
                if i == n - 1:
                    return True
                dist[e] = dist[s] + t
    return False

tc = int(input())
for _ in range(tc):
    n,m,w=map(int,input().split())
    graph = []
    for i in range(m):
        s,e,t = map(int,input().split())
        graph.append((s,e,t))
        graph.append((e,s,t))
    for i in range(w):
        s,e,t = map(int,input().split())
        graph.append((s,e,-t))

    tf = bellman_ford(1,n)

    if tf == True:
        print("YES")
    else:
        print("NO")