출처 : 백준
문제 보러가기 : 웜홀
해당 문제는 그래프의 간선이 음의 값을 가질 수 있는 문제이다. 따라서 벨만-포드 알고리즘을 이용해야 한다.
또한 문제에서 요구하는 답은 결국 그래프 내에 무한정으로 최단 거리가 감소하는 싸이클(negative cycle)이 존재하는지 여부를 묻는 문제이다.
Negative cycle의 존재여부를 구하는 방법
1. 모든 간선에 대해서 최단거리를 계산하는 과정을 시작점을 제외한 정점의 개수만큼 반복한다.
-> 모든 정점에 대한 최단거리를 구할 수 있다.
2. 한번 더 모든 간선에 대해서 최단거리를 계산하였을 때 최단거리가 갱신되면 negative cycle이 존재하는 것이다.
소스코드
|
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
|
#include<iostream>
#include<vector>
using namespace std;
#define INF 1e9
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc, n, m, w;
int s, e, t;
cin >> tc;
while (tc > 0) {
cin >> n >> m >> w;
int finder = 0;
vector<pair<pair<int, int>, int>> line;
vector<int> dist;
dist.resize(n + 1);
for (int i = 0; i < m; i++) {
cin >> s >> e >> t;
line.push_back({ {s,e},t });
line.push_back({ {e,s},t });
}
for (int i = 0; i < w; i++) {
cin >> s >> e >> t;
line.push_back({ {s,e},-t });
}
for (int i = 1; i <= n; i++) {
dist[i] = INF;
}
dist[1] = 0;
for (int i = 1; i <= n - 1; i++) {
for (int j = 0; j < line.size(); j++) {
int cost = line[j].second;
int start = line[j].first.first;
int end = line[j].first.second;
if (dist[end] > cost + dist[start]) {
dist[end] = cost + dist[start];
}
}
}
for (int j = 0; j < line.size(); j++) {
int cost = line[j].second;
int start = line[j].first.first;
int end = line[j].first.second;
if (dist[end] > cost + dist[start]) {
finder = 1;
break;
}
}
cout << (finder == 1 ? "YES" : "NO") << "\n";
tc--;
}
return 0;
}
|
cs |
댓글