[BOJ] 1865 웜홀(벨만 포드)

 

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

1865번: 웜홀

주제: 벨만포드 알고리즘

 

시간복잡도: O(|V|*|E|)

 

//boj 1865 웜홀
//알고리즘: 벨만포드
//시간 복잡도: O(|V||E|)

//오래 걸렸다.

/*
틀린 이유 -> if(d[From] == INF) continue;
이 부분은 모든 그래프가 연결 되어 있을 때만 의미가 있지,
그래프가 연결 되어 있지 않다면, 없어야 하는 조건이다.

그래야지 떨어져 있는 그래프에서의 음의 사이클을 찾을 수 있다
if(d[From] == INF) continue; 로 바로 넘어가 버리면
떨어져 있는 그래프의 상황은 아예 고려하지 않는 것이 된다

반례
1
6 4 4
1 2 1
2 3 1
4 5 1
6 5 1

2 1 -1
3 2 -1
5 4 -2
6 5 -1
				
*/


#include<bits/stdc++.h>

using namespace std;

int main()
{
	int INF = 1e9;

	int TC;
	cin >> TC;
	
	while(TC--)
	{	
		
		//준비 단계
		vector<pair<int, pair<int, int> > > edge;
		int N, M, W;
		cin >> N >> M >> W;
		
		int d[N+2]; //약간 걱정됨
		fill(d, d+N+1, INF); //초기화
		
		int S, E, T;
		for(int i = 0; i < M; i++)
		{
			cin >> S >> E >> T;
			
			edge.push_back({S,{E, T}});
			edge.push_back({E,{S, T}});
		}
		
		for(int i = 0; i < W; i++)
		{
			cin >> S >> E >> T;
			
			edge.push_back({S,{E, -T}});
		}
		//입력 완료
		
		d[1] = 0;
		
		int check = 0;
		
		//V 만큼 반복, 단, V번째에서 cycle이 발생하는지 확인 
		for(int i = 1; i <= N-1; i++) //N-1번 반복 시행 
		{
			for(int j = 0; j < edge.size(); j++) //1부터 N까지의 edge 실행 
			{
				int From = edge[j].first;
				int to = edge[j].second.first;
				int val = edge[j].second.second;
				
	
				if(d[to] > d[From] + val)
				{
					d[to] = d[From] + val;
					//printf("check %d %d %d -> %d\n",From, to, val, d[to]);
				}
			}
		}
		
		//대망의 N번째 -> 음의 사이클 확인 
		for(int j = 0; j < edge.size(); j++) //1부터 N까지의 edge 실행 
		{
			int From = edge[j].first;
			int to = edge[j].second.first;
			int val = edge[j].second.second;
			
			if(d[to] > d[From] + val)
			{
				check = 1;
				break;
			}
		}
		
		//결론 
		if(check == 1)
		{
			cout << "YES" << '\n';
		}
		else
		{
			cout << "NO" << '\n';			
		}
	}
}