백준 1865 c++ -[PlusUltraCode]

[필자 사고]

문제를 해석해 보니 다음과 같은 결론을 내렸다.

1. 출발해서 다시 원점으로 돌아와야 된다. => 사이클이 있다.

2. 웜홀을 통해 내가 쓴 시간보다 더 적은 시간을 사용해야 된다 => 음수 사이클이 있다.

 

이를 통해 음수 사이클을 대표적으로 판단할 수 있는 벨만포드 알고리즘이 떠올랐다. 

벨만포드 알고리즘을 간단하게 설명하겠다.

모든 간선들의 조사를 N-2번 조사한다. 그 후 마지막 한번도 모든 간선들을 조사 했을 때 Distance의 값중 하나가 바뀌게 된다면 음수 사이클이 존재한다는 것을 판별 할 수 있게 된다. 

 

[소스 코드] 

 

 

 

#include <iostream>
#include <vector>

using namespace std;

typedef struct Node {
	int start;
	int end;
	int weight;
}Node;

vector<Node> Arr;
vector<int> Distance;

int N, M, W;

bool BellMan_Ford() {
	Distance[1] = 0;
	for (int i = 0; i < N - 1; i++) {
		for (int adj = 0; adj < Arr.size(); adj++) {
			Node node = Arr[adj];
			int start = node.start;
			int end = node.end;
			int weight = node.weight;
			if (Distance[start] == 100000000)continue;	
			if (Distance[end] > Distance[start] + weight) {
				Distance[end] = Distance[start] + weight;

			}
		}
	}
	bool Cycle = false;

	for (int adj = 0; adj < Arr.size(); adj++) {
		Node node = Arr[adj];
		int start = node.start;
		int end = node.end;
		int weight = node.weight;
		if (Distance[start] == 100000000)continue;
		if (Distance[end] > Distance[start] + weight) {
			Distance[end] = Distance[start] + weight;
			Cycle = true;
			break;
		}
	}
	if (Cycle == true)return true;
	else return false;
}

void Input() {
	cin >> N >> M >> W;
	Arr.clear();
	Distance.clear();
	
	Distance.resize(N+1,10000000);

	for (int i = 0; i < M; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		Node node = { s,e,w };
		Node node2 = { e,s,w };
		Arr.push_back(node);
		Arr.push_back(node2);
	}
	for (int i = 0; i < W; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		w *= -1;
		Node node = { s,e,w };
		Arr.push_back(node);
	}
	

}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	
	for (int i = 0; i < T; i++) {
		
		Input();
	
		if (BellMan_Ford()) {
			cout << "YES" << '\n';
		}
		
		else {
			cout << "NO" << '\n';
		}
	}
}