문제
풀이
벨만-포드 알고리즘에 대한 문제이다. 다익스트라는 가중치가 양수로만 이루어져있을때 사용 가능한 반면, 시간 복잡도 O(|V| X |E|)인 벨만 - 포드는 음수일때도 사용이 가능하다. 벨만포드 알고리즘은 정점 갯수 N이 주어졌을 때, N-1번동안 모든 간선을 이동할 때마다 최저값을 갱신해나가는 것을 시작으로 하여, 그 이후 한번 더 갱신을 시도했을 때, 값이 바뀌는 경우가 있다 면, 그것은 음의 사이클(=계속해서 무한대로 -로 다가가는 경우)라고 하고, 갱신이 되지 않는다면 음의 가중치가 있을 때의 최저값을 보장한다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<vector>
#define endl "\n"
#define MAX 510
#define INF 987654321
using namespace std;
int N, M;
long long Dist[MAX];
vector<pair<pair<int, int>, int>> Edge;
void Input()
{
cin >> N >> M;
for (int i = 1; i <= N; i++) Dist[i] = INF;
for (int i = 0; i < M; i++)
{
int From, To, Cost;
cin >> From >> To >> Cost;
Edge.push_back(make_pair(make_pair(From, To), Cost));
}
}
void Solution()
{
Dist[1] = 0;
for (int i = 1; i <= N - 1; i++)
{
for (int j = 0; j < Edge.size(); j++)
{
int From = Edge[j].first.first;
int To = Edge[j].first.second;
int Cost = Edge[j].second;
if (Dist[From] == INF) continue;
if (Dist[To] > Dist[From] + Cost) Dist[To] = Dist[From] + Cost;
}
}
for (int i = 0; i < Edge.size(); i++)
{
int From = Edge[i].first.first;
int To = Edge[i].first.second;
int Cost = Edge[i].second;
if (Dist[From] == INF) continue;
if (Dist[To] > Dist[From] + Cost)
{
cout << -1 << endl;
return;
}
}
for (int i = 2; i <= N; i++)
{
if (Dist[i] == INF) cout << -1 << endl;
else cout << Dist[i] << endl;
}
}
void Solve()
{
Input();
Solution();
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("Input.txt", "r", stdin);
Solve();
return 0;
}
//출처: https://yabmoons.tistory.com/380 [얍문's Coding World..]
