백준_11657: 타임머신

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

11657번: 타임머신

위 문제는 음수 간선이 포함된 최단 거리 문제이다.

음수 간선의 순환이 포함되는 경우, 벨만 포드 최단 경로 알고리즘을 사용할 수 있다.

 

 

다익스트라와의 차이점:

다익스트라는 N-1번만큼 반복을 하되, 모든 간선을 다 확인하지 않고 특정 노드에 붙어있는 간선만 확인한다.

 

 

#https://www.acmicpc.net/problem/11657
n, m = map(int, input().split())
edges = []
for i in range(m):
    a, b, c = map(int, input().split())
    edges.append((a, b, c))

INF = 100000000
distance = [INF]*(n+1) # 시작 노드(1)에서 다른 노드들까지의 최단 경로
start = 1 # 출발 노드

def Bell_ford(start):
    distance[start] = 0
    for i in range(n): #start인 본인 노드를 제외
        for now, end, cost in edges:
            cost_all = distance[now] + cost
            if distance[now] != INF and distance[end] > cost_all:
                distance[end] = cost_all
                if i == n-1:
                    return 1 #음의 사이클이면 1 반환
    return 0

flag = Bell_ford(start)
print(distance[1:])

if flag == 1:
    print(-1)
else:
    for i in range(2, n+1):
        if distance[i] == INF:
            print(-1)
        else:
            print(distance[i])

 

포인트: 

INF일 경우 업데이트를 안한다. 왜냐하면 음의 값으로 업데이트 될 수 있기 때문이다.

음의 사이클인지 확인

 

참고: 

https://www.youtube.com/watch?v=Ppimbaxm8d8 

https://www.youtube.com/watch?v=obWXjtg0L64