[PS] BOJ 1865웜홀

##BOJ-1865 웜홀
https://www.acmicpc.net/problem/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.