BOJ-1865 웜홀
본래 벨만-포드 알고리즘은 방향그래프에서만 적용가능한 알고리즘이다.
하지만 본 문제에서는 웜홀만 방향이 있다고 설명한다.
따라서 우리는 지점과 지점사이에 가중치가 똑같은 두개의 간선을 생성한다.
그후 웜홀부터 지점까지의 간선을 음의 간선으로 추가하여 음의 회로가 있는지 판별하면 된다.
출발지가 음의 간선이 될려면 웜홀이 해당 출발지를 도착지로 지정해야 가능하기 때문에 이러한 경우에서만
검사를 하면 된다.
solution
#include<iostream>
#include<vector>
#include<list>
#define MAXN 100000
using namespace std;
vector<vector<pair<int, int> > > G;
int T, N, M, W;
vector<int> d;
bool is_negative_cycle(int pos) {
d[pos] = 0;
for (int i = 0; i < N; i++){
for (int j = 0; j < G.size(); j++){
for (auto it = G[j].begin(); it != G[j].end(); it++){
if (it->second != MAXN && d[it->first] > d[j] + it->second){
d[it->first] = d[j] + it->second;
if (i == N - 1){
return true;
}
}
}
}
}
return false;
}
int main() {
cin >> T;
while (T--){
cin >> N >> M >> W;
G.assign(N, vector<pair<int, int> >());
for (int i = 0; i < M; i++){
int from;
pair<int, int> p;
cin >> from >> p.first >> p.second;
p.first--;
G[from - 1].push_back(p);
G[p.first].push_back(make_pair(from - 1, p.second));
}
vector<bool> dst(N, 0);
for (int i = 0; i < W; i++){
int from;
pair<int, int> p;
cin >> from >> p.first >> p.second;
p.first--;
dst[p.first] = true;
p.second = -p.second;
G[from - 1].push_back(p);
}
bool b = true;
d.assign(N, MAXN);
for (int i = 0; i < N; i++){
if (dst[i]){
fill(d.begin(), d.end(), MAXN);
if (is_negative_cycle(i) == false){
b = false;
break;
}
}
}
if (!b){
cout << "NO" << endl;
}
else{
cout << "YES" << endl;
}
}
return 0;
}
Copyright (C) 2016 (KimBom) all rights reserved.
Related Posts
BOJ-11657 타임머신
BOJ-11657 타임머신
https://www.acmicpc.net/problem/11657
본 문제는 시간 C가 음수가 나올 수 있기 때문에, 벨만-포드 알고리즘을- BOJ-2252 줄 세우기
BOJ-2252 줄 세우기
https://www.acmicpc.net/problem/2252
본 문제는 단순히 입력을 인접리스트인 그래프로 만든뒤에, 위상정렬한 결과를
- BOJ-1707 이분그래프
BOJ-1707 이분그래프
아래의 사이트는 이분그래프를 판별하는 문제이다.
https://www.acmicpc.net/problem/1707
본 문제는, DFS 탐색