|
| 1 | +#include<bits/stdc++.h> |
| 2 | +#defineINF1e9// 무한을 의미하는 값으로 10억을 설정 |
| 3 | + |
| 4 | +usingnamespacestd; |
| 5 | + |
| 6 | +// 노드의 개수(N), 간선의 개수(M) |
| 7 | +// 노드의 개수는 최대 500개라고 가정 |
| 8 | +int n, m; |
| 9 | +// 모든 간선에 대한 정보를 담는 리스트 만들기 |
| 10 | +vector<pair<int, pair<int,int> > > edges; |
| 11 | +// 최단 거리 테이블 만들기 |
| 12 | +longlong d[501];// 오버 플로우 및 언더 플로우 방지 |
| 13 | + |
| 14 | +boolbf(int start) { |
| 15 | +// 시작 노드에 대해서 초기화 |
| 16 | + d[start] =0; |
| 17 | +// 전체 n - 1번의 라운드(round)를 반복 |
| 18 | +for (int i =0; i < n; i++) { |
| 19 | +// 매 반복마다 "모든 간선"을 확인하며 |
| 20 | +for (int j =0; j < m; j++) { |
| 21 | +int cur_node = edges[j].first; |
| 22 | +int next_node = edges[j].second.first; |
| 23 | +int edge_cost = edges[j].second.second; |
| 24 | +// 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우 |
| 25 | +if (d[cur_node] != INFand d[next_node] > d[cur_node] + edge_cost) { |
| 26 | + d[next_node] = d[cur_node] + edge_cost; |
| 27 | +// n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재 |
| 28 | +if (i == n -1)returntrue; |
| 29 | + } |
| 30 | + } |
| 31 | + } |
| 32 | +returnfalse; |
| 33 | +} |
| 34 | + |
| 35 | +intmain(void) { |
| 36 | + cin >> n >> m; |
| 37 | + |
| 38 | +// 모든 간선 정보를 입력받기 |
| 39 | +for (int i =0; i < m; i++) { |
| 40 | +int a, b, c; |
| 41 | + cin >> a >> b >> c; |
| 42 | +// a번 노드에서 b번 노드로 가는 비용이 c라는 의미 |
| 43 | + edges.push_back({a, {b, c}}); |
| 44 | + } |
| 45 | + |
| 46 | +// 최단 거리 테이블을 모두 무한으로 초기화 |
| 47 | +fill_n(d,501, INF); |
| 48 | + |
| 49 | +// 다익스트라 알고리즘을 수행 |
| 50 | +bool negative_cycle =bf(1);// 1번 노드가 시작 노드 |
| 51 | + |
| 52 | +if (negative_cycle) { |
| 53 | + cout <<"-1" <<'\n'; |
| 54 | +return0; |
| 55 | + } |
| 56 | +// 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리를 출력 |
| 57 | +for (int i =2; i <= n; i++) { |
| 58 | +// 도달할 수 없는 경우, -1을 출력 |
| 59 | +if (d[i] == INF) { |
| 60 | + cout <<"-1" <<'\n'; |
| 61 | + } |
| 62 | +// 도달할 수 있는 경우 거리를 출력 |
| 63 | +else { |
| 64 | + cout << d[i] <<'\n'; |
| 65 | + } |
| 66 | + } |
| 67 | +} |