BOJ 11657번: 타임머신

www.acmicpc.net/problem/11657

11657번: 타임머신

아이디어:

벨만-포드 알고리즘을 이용하여 최단경로를 구해야한다. 다익스트라 알고리즘은 간선의 가중치가 음수인 경우에는 사용하지 못하기 때문이다. 벨만-포드 알고리즘의 시간복잡도는 O(VE)이다.

벨만 - 포드 알고리즘은 존재하는 모든 간선을 V-1번 돌아보면서 이 간선을 통할 수도 있는 최단경로들의 거리를 갱신하는 것이다. 왜 V-1번 이냐면 최단 경로가 되려면 최대 V-1개의 간선을 통과하기 때문이다. 하지만 여기서! 이 문제처럼 음의 가중치를 가지고 있고, 음의 사이클이 가능한 벨만-포드 문제에서는 음의 사이클을 찾기 위해서 V번 돌아봐야 한다. 음의 사이클이 없다면 마지막 V번째에서 최단 거리가 갱신되지 않을 것이지만, 만약 음의 사이클이 존재한다면 V번째에서 최단 거리가 갱신될 것이기 때문이다.

m.blog.naver.com/kks227/220796963742

(참고)

구현하는 방법은 어렵지 않다. 그래도 아직 익숙하지 않으니 익숙해지려면 좀 더 많이 풀어봐야 할 것 같다. 시간복잡도는 다익스트라 알고리즘이 더 효율적이지만, 음수 가중치가 있는 경우에는 벨만-포드 알고리즘을 사용해야 한다!

import sys

N,M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    graph[A].append([B,C])
INF = 10**9
dist = [INF]*(N+1)
dist[1] = 0 #시작 정점

flag = False #음수 사이클 판단
for i in range(1,N+1): #모든 정점에 연결되어 있는 간선 N번 탐색
    for j in range(1, N+1):
        if (dist[j]==INF): continue #연결되지 않은 정점은 패스

        for adj in graph[j]:
            if (dist[j]+adj[1] < dist[adj[0]]):
                if (i==N):
                    flag = True #N번째에 최단경로 갱신되면 음수 사이클존재하는것
                dist[adj[0]] = dist[j]+adj[1]

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