[PS]BOJ 1865虫洞

#BOJ-1865虫洞
https://www.acmicpc.net/problem/1865
もともとベルマン・フォードアルゴリズムは方向図にのみ適用されるアルゴリズムだった.
しかし、本題は虫の穴だけが方向性があることを示している.
したがって,点と点の間に2本の重み付けが等しい幹線を生成する.
そして虫洞から地点までの幹線を負幹線に追加し,負回路があるか否かを判別する.
この場合にのみ、始点が負の幹線であるように始点を終点として指定することができる.
チェックすればいいです.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.