[백준] 11657 벨만포드

[백준] 11657 벨만포드 - 파이썬

bled 2021. 12. 19. 21:14

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

11657번: 타임머신

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

www.acmicpc.net

import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
distances = [INF] * (n+1)
edges = [list(map(int,input().split())) for _ in range(m)]
    
def bellman_ford(start):
    distances[start] = 0
    for i in range(n):
        for j in range(m):
            cur_node = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2] + distances[cur_node]
            if distances[cur_node] != INF and distances[next_node] > cost:
                if i == (n-1):
                    return True
                distances[next_node] = cost
    return False          
    
negative_cycle = bellman_ford(1)

if negative_cycle:
    print(-1)
else:
    for i in range(2, n+1):
        if distances[i] == INF:
            print(-1)
        else:
            print(distances[i])

https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/

벨만-포드 알고리즘 · ratsgo's blog

이번 글에서는 최단 경로(Shortest Path)를 찾는 대표적인 기법 가운데 하나인 벨만-포드 알고리즘(Bellman-Ford’s algorithm)을 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님과 역시 같은 대학

ratsgo.github.io

https://www.youtube.com/watch?v=Ppimbaxm8d8&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=13