BOJ 1965 웜홀

사용한 알고리즘

벨만포드 알고리즘, DFS

알고리즘 설명

도시를 노드로 구성하고 각 도시를 양방향 연결한다.
이 뒤에 웜홀과 같은 경우 그래프에 음의 가중치를 가지는 일반통행 u->v 연결을 진행한다.
이 뒤에 벨만포드 알고리즘을 적용한다.
벨만포드 알고리즘에서 N-1 edge에 적용한 뒤, N번째 업데이트는 음의 사이클을 가지는 경우이다.
음의 사이클과 연결되어 있는 노드를 dfs로 연결 시킨다.
시작점인 1번 노드가 음의 사이클과 연결되어 있는지 확인한다.

풀이

// baekjoon 1865 yechan
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> P;

const int MAX_N=501;
const int MAX_INF=1e9;

int TC, N, M, W, S, E, T;
vector<vector<P> > adj;
vector<bool> ncycle;

void dfs(int here) {
	ncycle[here]=true;
	for (int i=0; i<adj[here].size(); i++) {
		if (ncycle[adj[here][i].first]) continue;
		dfs(adj[here][i].first);
	}
}

int main() {
	scanf("%d", &TC);
	while (TC--) {
		scanf("%d%d%d", &N, &M, &W);
		adj = vector<vector<P> >(N+1);
		while (M--) {
			scanf("%d%d%d", &S, &E, &T);
			adj[S].push_back(P(E,T));
			adj[E].push_back(P(S,T));
		}
		while (W--) {
			scanf("%d%d%d", &S, &E, &T);
			adj[S].push_back(P(E,-T));
		}

		vector<int> dist(N+1, MAX_INF);

		ncycle = vector<bool>(N+1, false);

		dist[1]=0;
		for (int k=0; k<N; k++) {
			for (int i=1; i<=N; i++) {
				for (int j=0; j<adj[i].size(); j++) {
					int nx = adj[i][j].first;
					int nw = adj[i][j].second;
					if (dist[nx] > dist[i] + nw) {
						dist[nx] = dist[i] + nw;
						if (k == N-1) {
							ncycle[nx]=true;
							dfs(nx);
						}
					}
				}
			}
		}
		puts(ncycle[1] ? "YES":"NO");
	}
	return 0;
}