https://www.acmicpc.net/problem/11657
시간 1초, 메모리 128MB
input :
- N M(1 ≤ N ≤ 500)(1 ≤ M ≤ 6,000)
- A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)
output :
- 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력
- N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력
- 해당 도시로 가는 경로가 없다면 대신 -1을 출력
다익스트라와 비슷한 또다른 알고리즘으로 벨만 - 포드 알고리즘 문제이다.
처음에 보고 무슨 말인가 싶었는데.. 그냥 모든 간선에 대해 최단거리를 구하도록 하는 것을 n - 1 번 수행 한다. 그리고 이 최단 거리 값을 가지고,
다시 한 번 최단 거리 업데이트를 수행하는데 이때 갱신 되는 것이 존재한다면 사이클이 존재하는 것으로 보고 -1 을 출력하게 하는 것이다.
import sys
def bellman_ford():
# 최단 거리를 기록할 리스트를 초기화 한다.
# 모든 값들은 inf 로 무한으로 초기화 한다.
dist_list = [float('inf') for _ in range(n + 1)]
#시작 값은 1번 도시이기 떄문에 1번을 0으로 초기화 하고 시작.
dist_list[1] = 0
for i in range(n - 1):
# n - 1번 동안 최단 거리 업데이트를 시작한다.
for a, b, c in graph:
# 시작 노드 a , 도착 노드 b, 가는데 드는 비용 c
# 해서 b 까지의 최단 거리가, dis[a] + c 보다 작은지
# 비교해서 업데이트를 해준다.
dist_list[b] = min(dist_list[b], dist_list[a] + c)
return dist_list
def cycle():
for s, e, w in graph:
# 위에서 업데이트를 할 때 썼던 함수와 동일한 구조로
# 이 조건에 걸리면 바로 True를 리턴 하도록 한다.
if dist_list[e] > dist_list[s] + w:
return True
return False
n, m = map(int, sys.stdin.readline().split())
graph = []
for _ in range(m):
a, b, c = map(int, sys.stdin.readline().split())
graph.append((a, b, c))
dist_list = bellman_ford()
if cycle():
print(-1)
else:
for i in range(2, n+1):
print(dist_list[i] if dist_list[i] != float('inf') else -1)가장 특이한 것은, 어차피 모든 간선을 방문 하기 때문에 노드에 대한 간선으로 저장 하지 않고 그냥 한 배열에 저장한 후에 이를 다 꺼내서 확인 한다.
