[Python][백준 11657][벨만포드] 타임머신 - 컴도리돌이

반응형

11657번: 타임머신

---

풀이 과정

그래프 문제에서 노드간에 걸리는 시간이 음수가 포함했다? -> 벨만 포드

 

음수 간선에 관하여 최단 경로 문제는 다음과 같이 분류할 수 있다.

1. 모든 간선이 양수인 경우

2. 음수 간선이 있는 경우

  2-1)  음수 간선 순환은 없는 경우

  2-2)  음수 간선 순환이 있는 경우

벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있다. 또한 음수 간선의 감지할 수 있으며, 벨만 포드의 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느리다.

 

벨만 포드 알고리즘 과정

1. 출발 노드를 설정

2. 최단 거리 테이블을 초기화

3. 다음의 과정을 N-1번 반복

  3-1 ) 전체 간선 E개를 하나씩 확인한다.

  3-2 ) 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신

---

풀이 코드

n,m = map(int,input().split())
route = [list(map(int,input().split())) for _ in range(m)]
dist = [1e9 for _ in range(n+1)]
def bel() :
  dist[1] = 0 # start
  for i in range(n) :
    for cur,nex,weight in route :
      if dist[cur] != 1e9 and dist[nex] > dist[cur] + weight :
        dist[nex] = dist[cur] + weight
        if i == n-1 :
          return True
  return False

if bel() : print(-1)
else :
  for i in range(2,n+1) :
    if dist[i] != 1e9 : print(dist[i])
    else : print(-1)