[BOJ] 1865번 웜홀

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

 

 

 

 

벨만 포드 문제

 

근데 마지막 테케에서 시간초과

왜?

 

import sys
input = sys.stdin.readline

def solution():
    n, m, w = map(int, input().split())

    edges = []
    for _ in range(m):
        a, b, c = map(int, input().split())
        edges.append((a, b, c))
        edges.append((b, a, c))

    for _ in range(w):
        a, b, c = map(int, input().split())
        edges.append((a, b, -c))


    def bf(start):
        distance = [1e9] * (n+1)
        distance[start] = 0

        for i in range(n):
            for e in edges:
                a, b, c = e
                cost = distance[a] + c

                if distance[a] != 1e9 and distance[b] > cost:
                    distance[b] = cost

                    if i == n-1:
                        return True

        return False

    for i in range(1, n+1):
        if bf(i):
            return 'YES'

    return 'NO'


def main():
    t = int(input())

    for _ in range(t):
        print(solution())


main()

 

 

    for i in range(1, n+1):
        if bf(i):
            return 'YES'

    return 'NO'

 

이 부분 보라. 

모든 점에 대해서 벨만포드를 돌리고 있다. 

내가 작성한 벨만포드 알고리즘은 출발점이 특정한 한 점일 때 가능한 알고리즘이라, 그래프에서 음의 사이클이 있는지 여부를 판단하기 위해 모든 점에 대해서 반복문을 돌렸다.

그러니 시간초과 발생

 

 

만약 dist[N] 이 INF 라서 지나치게 되면, 뒤에 있는 cycle 의 유무를 판단할 수 없다. 

 

distance 배열에 INF 값을 설정하는 이유는 단절이 되었다는 뜻을 표시하기 위함이다. 

 

그래프에서 단순하게 음의 사이클 유무를 판단하는데는 distance 배열을 어떤 값으로 초기화해주어도 상관이 없다. 

왜냐하면 거리를 구하는 것이 아니라 마지막에서 음의 사이클이 존재할 때, 변화만 파악하는 것이기 때문이다. 

 

따라서 벨만 포드 알고리즘을 아래와 같이 작성하면 단 한번의 실행으로 음의 사이클을 판별할 수 있다. 

    def bf(start):
        distance = [0] * (n+1)
        distance[start] = 0

        for i in range(n):
            for e in edges:
                a, b, c = e
                cost = distance[a] + c

                if distance[b] > cost:
                    distance[b] = cost

                    if i == n-1:
                        return True

        return False

    if bf(1):
        return 'YES'