백준(BOJ) 1865 웜홀 **

벨 만 포드 방식을 알고 있다면 쉽게 풀 수 있는 문제이다.

내가 실 수 했던 점은
"만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능" 을 
"음수의 값을 가지는 노드가 있으면 가지면 YES"로 이해했다.

"모든 웜홀의 정보 S의 노드가 음수의 값을 가지면 YES"가 맞다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define MAX 40005
#define MOD 1000000007
#pragma warning(disable:4996)
using namespace std;

int t,n,m,w,a,b,c;
int map[505][505],cur[505];
bool tf[505];
vector v;

int getmin()
// 방문해야할 노드(tf[I]==false)중에 가장 작은 값을 반환.
{
	int tmp = MAX,ret=0;
	for (int i = 1; i <= n; i++)
		if (tf[i] == false && cur[i] < tmp)
		{
			tmp = cur[i];
			ret = i;
		}
	tf[ret] = true;
	return ret;
}

void bellman()
{
	while (1)
	{
		int tmp = getmin();
		if (!tmp)
			break;
		// 더 이상 방문할 노드가 없으면 끝낸다.

		for (int i = 1; i <= n; i++)
		{
			for (int i = 0; i < v.size(); i++)
			{
				if (cur[v[i]] > 0)
					break;
				if (i == v.size() - 1)
				{
					printf("YES\n");
					return;
				}
			}
			// 웜홀의 시작지점이 모두 음수의 값을 가진다면 YES 출력한다.

			if (cur[tmp] + map[tmp][i] < cur[i])
			{
				tf[i] = false;
				cur[i] = cur[tmp] + map[tmp][i];
			}
			// 만약에 값이 갱신되어진다면 다시 방문할 수 있도록 tf값을 false시킨다.
			// 다익스트라 알고리즘과 다른점이다.(덕분에 시간이 오래걸린다.)
		}
	}
	printf("NO\n");
	
}

int main()
{
	scanf("%d",&t);
	for (int i = 0; i < t; i++)
	{
		fill_n(&map[0][0], 505 * 505, MAX);
		fill_n(&cur[0], 505, MAX);
		fill_n(&tf[0], 505, 0);


		scanf("%d%d%d", &n, &m, &w);

		for (int k = 0; k < m; k++)
		{
			scanf("%d %d %d", &a, &b, &c);
			if (map[a][b] > c)
			{
				map[a][b] = c;
				map[b][a] = c;
			}
		}

		for (int k = 0; k < w; k++)
		{
			scanf("%d %d %d", &a, &b, &c);
			v.push_back(a);
			if (map[a][b] > -c)
				map[a][b] = -c;

		}
		// 입력을 받아온다.
		cur[1] = 0;
		// 시작위치는 어디 노드에서 시작하든지 상관없다.
		bellman();
		// 벨만포드 알고리즘을 돌린다.
	}

	return 0;
}