BOJ 11657 타임머신 python

도시의 개수 * 버스의 노선의 개수 만큼 반복문을 돌면서 노드 갱신.
N번째 for문에서도 dp에 갱신이 일어나면 flag에 체크(간선에 순환이 포함된 경우)

모든 노드를 갱신하려면 모든 간선에 대한 조회를 (1 ~ V-1) 번 수행해야 한다. 조회가 다 끝난 후에도 갱신이 일어나면 순환이 여부를 알 수 있다.

간선의 가중치가 음수인 경우에는 다익스트라 알고리즘을 적용할 수 없다. 벨만-포드 알고리즘은 시간 복잡도가 O(NM)인 대신, 간선의 가중치가 음수여도 적용 가능하다.

풀이 코드

import sys
rl = sys.stdin.readline
n, m = map(int, rl().split())
g = [list(map(int, rl().split())) for _ in range(m)]
 
dp = [sys.maxsize for _ in range(n+1)]
dp[1] = 0
flag = False
for i in range(n):
    for v, u, w in g:
        if dp[v] != sys.maxsize and dp[u]>dp[v]+w:
            dp[u]=dp[v]+w
            if i == n-1: flag = True
 
if flag: print(-1)
else:
    for i in range(2, n+1):
        if dp[i] == sys.maxsize: print(-1)
        else: print(dp[i])

문제

풀이

풀이 코드