✍ 문제

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

👏 풀이과정

이 문제는 Bellman-Ford 알고리즘을 사용하여 푸는 문제이다. Bellman-Ford 알고리즘은 음수를 가지는 간선(E)이 있고 시작점이 주어졌을때 모든 정점(V)에 대해 최소 거리를 찾아내는 알고리즘이다. 음수값을 가지는 간선이 있으므로 사이클이 돌 수 있어 계속해서 반복되는 것을 찾아낼 수 있다.시간복잡도는 O(VE)이다.

이 문제에서는 음수 사이클이 있는지만 확인하면 되는 문제이므로 시작점 상관없이 N번 반복했을때 True를 가지면 YES를 출력하면 된다. 여기서 모든 시작점을 다 비교할 필요는 없다. 어차피 N-1 번 반복하면 모든 정점에 대한 간선으로 최소 값을 확인 할 수 있고 여기서 한번더 반복해서 최소 값이 바뀌게 되면 음수 사이클이 돈다는 것을 알 수 있다.

import sys
def bf(start):
    for i in range(N):
        for j in range(M*2+W):
            pre_node = array_list[j][0]
            next_node = array_list[j][1]
            cost = array_list[j][2]
            if  distance[pre_node] + cost < distance[next_node]:
                distance[next_node] = distance[pre_node] + cost
                if i == N - 1:
                    return True

    return False


TC = int(sys.stdin.readline())

for _ in range(TC):
    N, M, W = map(int, sys.stdin.readline().split())
    array_list = []
    for _ in range(M):
        S, E ,T = map(int, sys.stdin.readline().split())
        array_list.append((S,E,T))
        array_list.append((E,S,T))

    for _ in range(W):
        S, E ,T = map(int, sys.stdin.readline().split())
        array_list.append((S,E,-T))

    distance = [int(1e9)]*(N+1)
    aa = bf(0)
    if aa == True:
        print("YES")
        continue
    print("NO")