[BOJ] 백준 1865번: 웜홀

SPFA + SLF 로 풀었지만 일반적인 벨만포드 알고리즘이 더 빠름

웜홀 시작점을 저장하여 탐색하며 update 횟수를 cycle 배열에 저장하여 노드 수 이상 업데이트 되면 음의 사이클

[!] 노드 수가 N개일때 N개를 전부 탐색하는 path는 n-1 개이다 n번 탐색이 된 경우는 n-1번 움직였을때보다 최소의 경로 비용을 뜻하므로 음의 간선이 있음

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <memory.h>
#include <math.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

void solve() {
	int n, m, w;

	vector<pii> v[501];
	vector<int> list;
	cin >> n >> m >> w;	
	int start;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
		v[b].push_back({ a,c });
	}
	for (int i = 0; i < w; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({ b,-c });
		list.push_back(a);
	}
	int flag = 0;
	for(auto start : list){
		deque<int> dq; 
		int dist[501];
		int cycle[501] = { 0, };
		cycle[start] = 1;
		fill(dist, dist + 501, 2e9);
		int inQ[501] = { 0, };
		dist[start] = 0;
		inQ[start] = 1;
		dq.push_back(start);
		while (!dq.empty()) {
			int node = dq.front(); dq.pop_front();
			inQ[node] = 0;
			for (auto nxt : v[node]) {
				int next = nxt.first;
				int cost = nxt.second;
				if (dist[next] > dist[node] + cost) {
					dist[next] = dist[node] + cost;
					cycle[next] += 1;
					if (cycle[next] >= n) {
						flag = 1;
						break;
					}
					if (!inQ[next]) {
						inQ[next] = 1;
						dq.push_back(next);
						if (dist[dq.front()] > dist[dq.back()]) {
							dq.push_front(dq.back());
							dq.pop_back();
						}
					}
				}
			}
		}
	}
	cout << (flag ? "YES\n" : "NO\n");
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int t;
	cin >> t;
	for (; t--;) {
		solve();
	}
}