백준 1865 웜홀

https://www.acmicpc.net/problem/1865

1865번: 웜홀

 

벨만 포드 알고리즘을 이용하는 문제다.

 

이 문제를 풀면서 배운점은 문제의식을 명확히 하라는 점이다.

 

벨만 포드는 다익스트라 알고리즘보다 시간복잡도(O(V*E) vs O(ElogE))가 크기 때문에 잘 사용하지 않는다.

 

하지만 다익스트라 알고리즘보다 정확해서 음의 가중치가 섞인 경로에서 최적 경로를 찾아낼 수 있고

 

음의 사이클의 유무도 파악할 수 있다. 결국은 Shortes Path Algorithm이라서 경로를 찾는 알고리즘이다.

 

하지만 이 문제는 음의 사이클 형성여부만 확인하면 된다.

 

경로를 구하듯이 음의 값을 찾으려면 모든 정점을 다 돌아야겠지만, 음의 사이클만 확인하려고하면...

 

시작점이 뭐가됐든 상관없다.

 

bool bellman_ford(int src) 함수에서 fill을 주목하자. 0으로 초기화를 했다. 보통 INTMAX로 초기화한다. 왜냐하면

 

시작점으로부터 단절되어있다는 걸 표현하기 위해서이다. 하지만 이 문제는 시작점으로부터 단절된 건 상관없고

 

음의 사이클이 형성되는지만 관심있다. 그러므로 저 값을 -1로하든, -999로하든 상관없다. 

/* 웜홀 */

#include <iostream>
#include <algorithm>
#include <vector>
#include <vector>
#include <cstring>
#include <queue>

#define ll long long int
#define pp pair<ll, ll>

using namespace std;

void init();
void input();
void solve();

struct edgeNode {
	int src, des, weight;
	edgeNode(int a, int b, int c) {
		src = a;
		des = b;
		weight = c;
	}
};

int N, M, W;
int dist[505];
vector<edgeNode> edge;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int tt; cin >> tt;
	for (int i = 0; i < tt; i++) {
		init();
		input();
		solve();
	}
	return 0;
}

void init() {
	edge.clear();
}

void input() {
	cin >> N >> M >> W;
	for (int i = 0; i < M; i++) {
		int a, b, c; cin >> a >> b >> c;
		edge.push_back(edgeNode(a, b, c));
		edge.push_back(edgeNode(b, a, c));
	}

	for (int i = 0; i < W; i++) {
		int a, b, c; cin >> a >> b >> c;
		edge.push_back(edgeNode(a, b, -c));
	}
}

bool bellman_ford(int src) {
	fill(&dist[0], &dist[505], 0);
	dist[src] = 0;

	for (int i = 1; i <= N - 1; i++) {
		for (auto node : edge) {
			if (dist[node.des] > dist[node.src] + node.weight) {
				dist[node.des] = dist[node.src] + node.weight;
			}
		}
	}

	for (auto node : edge) {
		if (dist[node.des] > dist[node.src] + node.weight) {
			return true;
		}
	}
	
	return false;
}

void solve() {
	if (bellman_ford(1) == true) {
		cout << "YES\n";
		return;
	}
	cout << "NO\n";
	return;
}