코드 # 음의 가중치 존재 # 음의 사이클이 존재한다고 가정하면, 다익스트라를 사용했을 때 가중치가 음의 무한인 노드가 생긴다. # 따라서 다익스트라 알고리즘 사용 불가 # 플로이드-워셜 알고리즘, 벨만-포드 알고리즘 사용 가능 # 시간복잡도 O(VE)인 벨만 포드 알고리즘 채택 import sys input = sys.stdin.readline INF = 987654321 n,m = map(int, input().split()) graph = [] visited = [INF]*(n+1) for _ in range(m): x,y,z = map(int, input().split()) graph.append((x,y,z)) def bellman_ford(start): visited[start] = 0 # 출..
