boj-1865 웜홀

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

문제 소개

월드나라에는 n개의 지점이 있고, 그 사이에 m개의 도로와 w개의 웜홀이 있다. 도로는 방향이 없으며 웜홀은 방향이 있다.

웜홀은 도로와 반대로 시간이 거꾸로 간다.

한 지점에서 출발을 하여서 다시 출발을 하였던 위치로 돌아왔을 때, 출발 때보다 시간이 되돌아가 있는 경우가 있는지 판별한다.

테스트 케이스의 개수 t가 주어지고, 각 테스트 케이스에는 지점의 개수, 도로와 웜홀에 대한 정보가 주어진다.

문제 풀이

음수 간선인 웜홀이 존재하여 벨만 포드 알고리즘을 이용하여 풀이하였다.

함수 Bellman_Ford 내에서 마지막에 최단 거리가 갱신된다면 문제에서 요구하는 조건의 달성이 가능하므로 true를, 갱신되지 않는다면 false를 반환하도록 하였다.

코드

#include <iostream>
#include <vector>

int MAX = 987654321;

// 간선 구조체
struct Edge {
	int s;
	int e;
	int t;
	Edge(int x, int y, int z) {
		s = x;
		e = y;
		t = z;
	}
};

bool Bellman_Ford(std::vector<int>& dist, int n, std::vector<Edge>& edge) {
	dist[1] = 0;
	for (int i = 1; i <= n - 1; i++) {
		for (int j = 0; j < edge.size(); j++) {
			int s = edge[j].s;
			int e = edge[j].e;
			int t = edge[j].t;

			if (t > 0) {
				if (dist[s] != MAX && dist[s] + t < dist[e]) {
					dist[e] = dist[s] + t;
				}
				if (dist[e] != MAX && dist[e] + t < dist[s]) {
					dist[s] = dist[e] + t;
				}
			}
			else {
				if (dist[s] != MAX && dist[s] + t < dist[e]) {
					dist[e] = dist[s] + t;
				}
			}

		}
	}

    // 음수 사이클 존재 유무 판별
	for (int j = 0; j < edge.size(); j++) {
		int s = edge[j].s;
		int e = edge[j].e;
		int t = edge[j].t;

		if (t > 0) {
			if (dist[s] != MAX && dist[s] + t < dist[e]) {
				dist[e] = dist[s] + t;
				return true;
			}
			if (dist[e] != MAX && dist[e] + t < dist[s]) {
				dist[s] = dist[e] + t;
				return true;
			}
		}
		else {
			if (dist[s] != MAX && dist[s] + t < dist[e]) {
				dist[e] = dist[s] + t;
				return true;
			}
		}
	}

	return false;
}

int main() {
	using namespace std;
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int n, m, w;
		cin >> n >> m >> w;

		vector<int> dist(n + 1, 0);     // 최단 거리 벡터
		vector<Edge> edge;              // 간선 벡터

        // 도로 간선 정보 입력
		for (int j = 0; j < m; j++) {
			int s, e, t;
			cin >> s >> e >> t;
			edge.push_back(Edge(s, e, t));
		}

        // 웜홀은 가중치를 음수로 하여 입력
		for (int j = 0; j < w; j++) {
			int s, e, t;
			cin >> s >> e >> t;
			edge.push_back(Edge(s, e, -t));
		}

        // 벨만 포드 알고리즘 수행에 따라 결과 출력
		if (Bellman_Ford(dist, n, edge)) {
			cout << "YES" << '\n';
		}
		else {
			cout << "NO" << '\n';
		}
	}

	return 0;
}