티스토리 뷰
https://www.acmicpc.net/problem/11657
Bellman ford
시간복잡도 : O(E*V)
특징 : 모든 간선에 대해서 확인함.
(마지막 n번 루프에서 값이 갱신되면 음의 싸이클 존재한다)
#include<iostream> #include<cstdio> #include<string.h> #include<vector> #include<algorithm> #include<queue> using namespace std; #define MY_MAX 987654321 vector<pair<int, pair<int, int>>> map; int visit[501]; int n, m; int flag; void input() { scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); map.push_back(make_pair(a, make_pair(b, c))); } } void algo() { for (int i = 2; i <= n; i++) { visit[i] = MY_MAX; } for (int i = 0; i < n; i++) { int len = map.size(); for (int j = 0; j < len; j++) { int start = map[j].first; int next = map[j].second.first; int cost = map[j].second.second; if (visit[start] != MY_MAX){ if (visit[next] > visit[start] + cost) { visit[next] = visit[start] + cost; if (i == n - 1){ flag = 1; } } } } } } void output() { if (flag != 0) { printf("-1\n"); } else { for (int i = 2; i <= n; i++) { if (visit[i] == MY_MAX) { printf("-1\n"); } else { printf("%d\n", visit[i]); } } } } int main() { input(); algo(); output(); return 0; } |