[11657번] 타임머신 (그래프, 최단거리, 벨만 포드 알고리즘)

11657번: 타임머신

 

벨만 포드

• 최단 거리를 구하는 알고리즘
• 음수간선 OK
• 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음
• O(VE)

기출

• 음수사이클이 있는 지 체크하는 문제 → 시간여행, 과거, 웜홀
• 음수간선, 시작점이 있고 최단거리 구하는 문제

과정

1. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화
2. 모든 에지를 확인해 정답 리스트 업데이트
3. 음수 사이클 유무 확인 : 모든 에지를 한 번씩 다시 사용해 업데이트 되는 노드가 발생하는지 확인

업데이트 조건과 반복

- 최단거리 리스트에서 업데이트 반복 횟수 : N-1
    (노드의 개수가 N이고, 음수 사이클이 없을때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수)
- D[s] != ∞ && D[e]>D[s]+w 일때 D[e] = D[s]+ w로 리스트의 값을 업데이트
- 업데이트 반복 횟수가 K번 ➡️ 해당 시점에 정답 리스트의 값은 시작점에서 K개의 에지를 사용했을 때 각 노드에 대한 최단 거리

 

풀이

자꾸 출력초과가 뜨는 원인은 '1번 도시에서 다른 도시로 가는 길목에 음수 사이클이 존재하는데도 모든 도시로 가는 시간을 굳이 출력'하고 있기 때문입니다. 보통은 아래 둘 중 하나가 원인이므로 꼼꼼히 확인해주세요.

1. 시간의 합이 자료형이 감당할 수 없을 정도로 커지는 경우. Python인 경우에는 정수 간의 연산에서 별도의 제한은 없기 때문에 문제가 되지 않습니다.
2. INF 값이 충분히 크지 못한 경우. 시간이 매우 걸리는 경로로 가더라도 INF 값을 넘지 못하도록 크게 잡으셔야 합니다. (제가 여기에 걸려서 코드 수정만 계속 했습니다)

"""
벨만-포드

N개의 도시(1~500), 한 도시에서 출발해 다른 도시에 도착하는 버스 M개(1~6,000)
A 시작도시 B 도착도시(1~N)  C 걸린시간(-10,000~10,000)

1번 도시에서 출발해 나머지 도시로 가는 가장 빠른 시간

시간을 무한히 오래전으로 되돌릴 수 있으면 1번째 줄에 -1출력 (음수간선싸이클 있으면)
아니면 n-1개 줄에 걸쳐 각줄의 1번 도시에서 출발해 2번 도시, 3번 도시,...,N번 도시로 가는 가ㅏㅇ 빠른 시간 순서대로 출력
경로 없으면 -1 출력
"""

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

# 에지 리스트
graph = []
for i in range(m):
    u, v, w = map(int, input().split())
    graph.append((u, v, w))

# print(graph)

# 최단 경로 리스트
d = [sys.maxsize] * (n+1)

d[1] = 0

# print(d)


cycleYn = False

for _ in range(n-1):
    for start, end, weight in graph:
        if d[start] != sys.maxsize:
            d[end] = d[start] + weight if d[end] > d[start] + weight else d[end]

for start, end, weight in graph:
    if d[start] != sys.maxsize and d[end] > d[start] + weight:
        cycleYn = True

# print(d)

if cycleYn:
    print(-1)
else:
    for i in range(2, n+1):
        if d[i] != sys.maxsize:
            print(d[i])
        else:
            print(-1)

 

글 읽기 - INF 크기를 충분하게 크게 잡으셔야 합니다.