[Baekjoon Online Judge] 백준 11657번 타임머신(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 11657번 타임머신

(Python)

(글쓴날 : 2020.06.12)

 

---

* Baekjoon Online Judge, 백준 11657번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 11657번 타임머신

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/11657

11657번: 타임머신

---

2) 풀이 과정

* 시간 복잡도 : O(EV)

 

N개의 도시와 도시 구간 별 M개의 버스 시간이 주어질 때, 1번 도시에서 나머지 도시로 가는 최소 시간을 구하는 문제입니다.

단, 갈 수가 없는 도시는 -1로 표시하며, 시간에 음수도 포함되어 있으므로 만약 시간이 음의 무한대로 줄어드는 구간이 존재할 경우 -1을 출력 후 종료합니다.

 

저의 경우, 벨만 포드 알고리즘을 적용하였고, Python을 사용했습니다.

우선, 주어지는 정보들을 인접 리스트로 구현한 뒤, 벨만 포드 알고리즘을 적용하여 음의 사이클이 존재하는지 판단하였고, 음의 사이클이 없을 시 최소 시간을 출력하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
def bellmanFord():
    global isPossible
 
    for repeat in range(N):
        for i in range(1, N+1):
            for wei, vec in adjList[i]:
                if dist[i] != INF and dist[vec] > dist[i] + wei:
                    dist[vec] = dist[i] + wei
                    if repeat == N-1:
                        isPossible = False
 
N, M = map(int,input().split())
adjList = [[] for _ in range(N+1)]
INF = 2147483647
dist = [INF] * (N+1)
dist[1] = 0
isPossible = True
 
for _ in range(M):
    a,b,c = map(int,input().split())
 
    adjList[a].append((c,b))
 
bellmanFord()
 
if not isPossible:
    print(-1)
else:
    for d in dist[2:]:
        print(d if d !=INF else -1)

---