어흥
[백준 1865] 웜홀 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/1865
1. 주의할 점
- 음의 가중치인 간선이 존재하기 때문에, 벨만포드 알고리즘을 사용한다
- 시작 Node가 정해져 있지 않아서 Dist[1] = 0, 나머지 Dist값은 전부 MAX로 초기 설정하고 시작하면 안된다 -> Dist 갱신할 때 Dist[next]!=MAX와 같은 조건도 없어야 한다
- 매 TC마다 V[]와 Dist[]를 초기화한다
2. 구현
- 도로의 경우 양방향, 웜홀을 단방향이며 가중치의 값을 음수로 V[]에 저장한다
- N-1번 동안 Dist를 갱신하고, N번째에도 Dist가 갱신된다면 음의 사이클이 존재한다고 판단하여 YES를 출력하고, 음의 사이클이 없다면 NO를 출력한다
#define MAX 9876543210
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct info {
int idx;
long long val;
};
info tmp;
vector<info> v[501];
long long dist[501];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int test, node, edge, warmhole, s, e;
long long val;
cin >> test;
for (int t = 0; t < test; t++) {
cin >> node >> edge >> warmhole;
for (int i = 1; i <= node; i++) {
v[i].clear();
dist[i] = MAX;
}
for (int i = 0; i < edge; i++) {
cin >> s >> e >> val;
tmp.val = val;
tmp.idx = e;
v[s].push_back(tmp);
tmp.idx = s;
v[e].push_back(tmp);
}
for (int i = 0; i < warmhole; i++) {
cin >> s >> e >> val;
tmp.idx = e;
tmp.val = -val;
v[s].push_back(tmp);
}
bool cycle = false;
for (int i = 1; i <= node; i++) {
for (int j = 1; j <= node; j++) {
int from = j;
for (int k = 0; k < v[from].size(); k++) {
int next = v[from][k].idx;
int nv = v[from][k].val;
if (dist[next] > dist[from] + nv) {
dist[next] = dist[from] + nv;
if (i == node) {
cycle = true;
break;
}
}
}
if (cycle) break;
}
if (cycle) break;
}
if (cycle) cout << "YES\n";
else cout << "NO\n";
}
system("pause");
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 3108] 로고 (C++) (2) | 2020.05.06 |
---|---|
[백준 9370] 미확인 도착지 (C++) (0) | 2020.05.06 |
[백준 13334] 철로 (C++) (0) | 2020.05.06 |
[백준 1007] 벡터 매칭 (C++) (2) | 2020.05.05 |
[백준 1005] ACM Craft (C++) (0) | 2020.05.05 |
Comments