File tree Expand file tree Collapse file tree 1 file changed +49
-0
lines changed
Expand file tree Collapse file tree 1 file changed +49
-0
lines changed Original file line number Diff line number Diff line change 1+ import sys
2+ input = sys .stdin .readline
3+ INF = int (1e9 ) # 무한을 의미하는 값으로 10억을 설정
4+
5+ # 노드의 개수, 간선의 개수를 입력받기
6+ n , m = map (int , input ().split ())
7+ # 모든 간선에 대한 정보를 담는 리스트 만들기
8+ edges = []
9+ # 최단 거리 테이블을 모두 무한으로 초기화
10+ distance = [INF ] * (n + 1 )
11+
12+ # 모든 간선 정보를 입력받기
13+ for _ in range (m ):
14+ a , b , c = map (int , input ().split ())
15+ # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
16+ edges .append ((a , b , c ))
17+
18+ def bf (start ):
19+ # 시작 노드에 대해서 초기화
20+ distance [start ] = 0
21+ # 전체 n - 1번의 라운드(round)를 반복
22+ for i in range (n ):
23+ # 매 반복마다 "모든 간선"을 확인하며
24+ for j in range (m ):
25+ cur_node = edges [j ][0 ]
26+ next_node = edges [j ][1 ]
27+ edge_cost = edges [j ][2 ]
28+ # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
29+ if distance [cur_node ] != INF and distance [next_node ] > distance [cur_node ] + edge_cost :
30+ distance [next_node ] = distance [cur_node ] + edge_cost
31+ # n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
32+ if i == n - 1 :
33+ return True
34+ return False
35+
36+ # 벨만 포드 알고리즘을 수행
37+ negative_cycle = bf (1 ) # 1번 노드가 시작 노드
38+
39+ if negative_cycle :
40+ print ("-1" )
41+ else :
42+ # 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리를 출력
43+ for i in range (2 , n + 1 ):
44+ # 도달할 수 없는 경우, -1을 출력
45+ if distance [i ] == INF :
46+ print ("-1" )
47+ # 도달할 수 있는 경우 거리를 출력
48+ else :
49+ print (distance [i ])
You can’t perform that action at this time.
0 commit comments