Boj 1865) 웜홀

문제

백준 1865

설명

간단한 음수 사이클 찾기 문제처럼 보이지만 시작점이 없다. 그래서 만약 벨만포드를 그대로 쓰고 시작지점을 임의로 잡으면, 시작지점으로부터 도달 불가능한 구역에서 발생하는 음수 사이클을 찾을 수 없다. 이를 해결하기 위해선 각각의 정점을 시작점으로 두어 \(\vert \mathrm{V} \vert\) 번 벨만포드를 시행할 수도 있지만 이는 시간복잡도 상 너무 느리다.

대신 벨만포드를 변형해서 모든 정점을 시작점으로 두어 수행하면 기존의 시간복잡도를 유지하면서 문제를 해결할 수 있다.

• 만약 모든 가중치가 양수라면 각 정점까지의 거리는 0 이 되어 의미가 없다.
• 하지만 음수인 가중치가 하나라도 존재한다면, 거리가 음수인 정점과 연결된 간선에서 Edge Relaxation 이 일어날 여지가 있다. 이것이 n 번째 루프에서도 일어난다면 음수사이클이 된다.

음수 가중치가 있으면 임의의 정점부터의 거리가 의미가 있게 된다는걸 알려주는 좋은 문제인듯 하다.

시간 복잡도

O(\(\vert \mathrm{E} \vert \vert \mathrm{V} \vert\))

코드

struct E { int d, w; };
std::vector<E> lines[501];
int n;

int distTB[501];
bool bellman(int start)
{
	// 모든 정점을 균등하게 두어, 모든 정점에서부터 탐색을 시작한다.
	fill(distTB, distTB + n + 1, 0);
	
	bool updated = false;	
	for (int i = 0; i < n; i++)
	{
		updated = false;
		for (int s = 1; s <= n; s++)
		{
			for (auto& l : lines[s])
				if (distTB[l.d] > distTB[s] + l.w)
				{
					distTB[l.d] = distTB[s] + l.w; // edge relaxation
					updated = true;
				}
		}
		if (updated == false) break;
	}
	return updated != true;
}

int main()
{
	int T; cin >> T;
	while (T--)
	{
		fill(lines, lines + n + 1, std::vector<E>());
		int m, w; cin >> n >> m >> w;
		for (int i = 0; i < m; i++)
		{
			int s, e, t; 
			cin >> s >> e >> t;
			lines[s].push_back({ e, t });
			lines[e].push_back({ s, t });
		}
		for (int i = 0; i < w; i++)
		{
			int s, e, t;
			cin >> s >> e >> t;
			lines[s].push_back({ e, -t });
		}
		cout << (!bellman(1) ? "YES" : "NO" ) << '\n';
	}
}