[C++] 백준 1865번: 웜홀

 

1865번: 웜홀

음의 가중치를 갖는 그래프에서 최단거리를 계산하는 문제다. 알고리즘 분류는 벨만-포드라고 되어 있지만, 플로이드-와샬을 이용해 문제를 풀었다. 아마 시간복잡도는 비슷하지만 코드는 훨씬 간결할 것이다. 플로이드-와샬 알고리즘에 대한 설명은 다음 블로그를 참고했다.

24. 플로이드 와샬(Floyd Warshall) 알고리즘

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"
#define VI vector<int>
#define VVI vector<VI>
#define VVVI vector<VVI>

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	TC(T) {
		int N, M, W;
		cin >> N >> M >> W;
		VVI adj(N, VI(N, INF));
		FOR(i, N)
			adj[i][i] = 0;
		FOR(i, M) {
			int S, E, T;
			cin >> S >> E >> T;
			if (T < adj[S - 1][E - 1])
				adj[S - 1][E - 1] = adj[E - 1][S - 1] = T;
		}
		FOR(i, W) {
			int S, E, T;
			cin >> S >> E >> T;
			if (-T < adj[S - 1][E - 1])
				adj[S - 1][E - 1] = -T;
		}

		FOR(via, N) FOR(from, N) FOR(to, N)
			if (adj[from][to] > adj[from][via] + adj[via][to])
				adj[from][to] = adj[from][via] + adj[via][to];

		FOR(i, N)
			if (adj[i][i] < 0) {
				cout << "YES" << EL;
				goto NEXT_CASE;
			}
		cout << "NO" << EL;
	NEXT_CASE:;
	}

	return 0;
}