[백준] 11657번:타임머신 (Python 파이썬)

[백준] 11657번:타임머신 (Python 파이썬)

반응형

문제

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

풀이 및 소스코드

벨만포드 알고리즘으로 푸는 문제이다.

어려워 ...

다익스트라와의 차이점은 매 반복마다 모든 간선을 확인한다는 것

다익스트라는 방문하지 않는 노드 중에서 최단 거리가 가장 가까운 노드만을 방문

import sys input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) edges = [] #간선에 대한 정보 담는 리스트 dist = [INF]*(n+1) for _ in range(m): u, v, w = map(int, input().split()) edges.append((u,v,w)) def bf(start): dist[start] = 0 for i in range(n): for j in range(m): node = edges[j][0] next_node = edges[j][1] cost = edges[j][2] if dist[node]!=INF and dist[next_node]>cost+dist[node]: dist[next_node] = dist[node]+cost if i == n-1: #정점의 끝인데 계속 값이 갱신되면 음수 순환 존재. return True return False n_c = bf(1) if n_c: print("-1") else: for i in range(2, n+1): if dist[i] == INF: print("-1") else: print(dist[i])

반응형

from http://jainn.tistory.com/200 by ccl(A) rewrite - 2021-08-11 18:00:22