[백준] 11657 타임머신 python

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

11657번: 타임머신

벨만 포드 알고리즘을 사용하는 문제이다. 알고리즘에 대한 자세한 내용은 아래 링크로 달아놓겠다.

# import sys; input = sys.stdin.readline
INF = 20_000_000_000

def bf(start):
    global dist, N, M, edges
    dist[start] = 0

    for i in range(N):
        for j in range(M):
            cur, next, cost = edges[j]

            if dist[cur] != INF and dist[next] > dist[cur] + cost:
                dist[next] = dist[cur] + cost
                if i == N - 1:
                    return True
    return False


def main():
    global dist, N, M, edges

    N, M = map(int, input().split())
    edges = []
    for _ in range(M):
        a, b, c = map(int, input().split())
        edges.append((a, b, c))

    dist = [INF for _ in range(N + 1)]
    cycle = bf(1)
    if cycle:
        print("-1")
    else:
        for i in range(2, N+1):
            if dist[i] == INF:
                print("-1")
            else:
                print(dist[i])


if __name__ == "__main__":
    main()

https://www.youtube.com/watch?v=Ppimbaxm8d8