백준 1865 : 웜홀

이거 한참 해메고, 또 의미를 해석하는 데에도 시간을 많이 썼다.

이는 벨만 포드 알고리즘의 "거리 계산"에 집중했기 때문으로, 이 문제에서는 그것을 요구하는 것이

아니었다.... 이 문제에서는 결국 "갱신 여부"에 집중하므로, d[i]=INF?라는 조건문을 빼버려야 하며(그러면

애초에 갱신이 안되므로) 더 나아가 애초에 d[i]를 INF로 갱신 안 해도 갱신 여부만을 판단하는 데에는 아무 문제가 없다.

그렇게 질문 계시판을 참조하여 얻은 코드는 다음과 같다:

#include<bits/stdc++.h>
#define INF 1e9
using namespace std;
vector<pair<pair<int, int>, int> > a;
long long int TC, N, M, W, d[501];
bool bellman_ford(void){
	for(int i=1;i<=N;i++){
		for(int j=0;j<a.size();j++){
			int now=a[j].first.first;
			int next=a[j].first.second;
			int cost=a[j].second;
			if(d[next]>d[now]+cost){
				d[next]=d[now]+cost;
				if(i==N){
					return true;
				}
			}
		}
	}
	return false;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> TC;
	for(int r=1;r<=TC;r++){
		cin >> N >> M >> W;
		for(int i=1;i<=M+W;i++){
			int S, E, T;
			cin >> S >> E >> T;
			if(i<=M){
				a.push_back(make_pair(make_pair(E, S), T));
				a.push_back(make_pair(make_pair(S, E), T));
			}
			else{
				a.push_back(make_pair(make_pair(S, E), -T));
			}
		}
		if(bellman_ford()==true) cout << "YES" << '\n';
		else cout << "NO" << '\n';
		while(!a.empty()) a.pop_back();
	}
}

이거 AC 받으려 이상한 짓도 해 봤다. 뭐 cin tie를 푼다든지 뭐.... 결론은 그게 아니었지만.

고정 관념에서 벗어나자는 것이 오늘 "웜홀"의 결론이다.