11657 - 타임머신
📌 문제
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.
1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.
📋 코드
INF = int(1e9)
def ford(start):
global cycle
distance[start] = 0
for i in range(N):
for j in range(1, N+1):
for now, cost in graph[j]:
if distance[j] <= INF and distance[now] > distance[j] + cost:
distance[now] = distance[j] + cost
if i == N-1:
cycle = True
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
distance = [INF for _ in range(N+1)]
for _ in range(M):
a, b, c = map(int, input().split())
graph[a].append([b, c])
cycle = False
ford(1)
if cycle:
print(-1)
else:
for dist in distance[2:]:
print(-1 if dist == INF else dist)💡 한마디
C가 음수인 경우도 존재하기 때문에 다익스트라가 아닌 벨만 포드 알고리즘을 이용해서 풀었다.
