[Python] 백준 11657번 - 타임머신

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

11657번: 타임머신

 

벨만포드 코드에 문제가 있는데 모르겠어서 친구랑 스터디할 때 상의했다.

for문을 세 번 돌려야 하는데 난 두 번만 돌려서 문제가 생겼다.

 

 

for i in range(1, n+1) : 간선 탐색을 위한 for문 (아래 for문을 n번 반복)

for a in range(1, n+1) : 노드 탐색을 위한 for문 (모든 엣지에 대해서 한 턴을 돌림)

 

노드가 n개일 때 최악의 경우, 간선이 n-1번에 걸쳐서 연결이 된다.

모든 엣지에 대한 탐색을 n번 수행해서 만약 n번째에도 새로운 엣지가 갱신이 된다면,

=> 사이클이 존재한다는 뜻.

 

import sys
input = sys.stdin.readline

def bf(start):
    dist[start] = 0
    for i in range(1, n+1): #간선 탐색을 위한 for문. 간선이 n-1개여야 사이클 x.
        for a in range(1, n+1): #노드 탐색을 위한 for문
            for next, time in graph[a]:
                if dist[a] != float('inf') and dist[next] > dist[a] + time:
                    dist[next] = dist[a] + time
                    if i == n: #n-1번 이후에도 값이 갱신되면 음수 사이클 존재.
                        return True #사이클 존재.
    return False

n, m = map(int, input().split())
graph = [[] for i in range(n+1)]
dist = [float('inf') for i in range(n+1)]
for i in range(m):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    #dist[b] = c

negative_cycle = bf(1)
if negative_cycle:
    print(-1)
else:
    for i in range(2, n+1):
        if dist[i] == float('inf'):
            print(-1)
        else:
            print(dist[i])