[백준 C++] 1865번: 웜홀

1. 문제

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

1865번: 웜홀

 

2. 알고리즘 분류

• 그래프 이론
• 벨만-포드

 

3. 소스 코드

#include <iostream>
#include <vector>

#define INF 987654321

using namespace std;

struct edge {
	int s, e, t;
};

// N : 지점의 수, M : 도로의 개수, W : 웜홀의 개수
int N, M, W;
vector<edge> edges;

// 벨만 코드 알고리즘
bool bellmanFord(int n) {
	// 거리 배열 생성
	vector<int> dist(n + 1, INF);

	// 시작점 거리 0으로 세팅
	dist[1] = 0;

	// 노드의 수 만큼 반복
	for (int i = 0; i < n; i++) {
		// 모든 경로를 탐색하면서 거리 갱신
		for (int pos = 0; pos < edges.size(); pos++) {
			int s = edges[pos].s;
			int e = edges[pos].e;
			int t = edges[pos].t;

			if (dist[s] + t < dist[e]) dist[e] = dist[s] + t;
		}
	}

	// 한번 더 경로 탐색하면서, 거리가 갱신된다면 음수 순환 존재
	for (int pos = 0; pos < edges.size(); pos++) {
		int s = edges[pos].s;
		int e = edges[pos].e;
		int t = edges[pos].t;

		if (dist[e] > dist[s] + t) return true;
	}

	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// TC : 테스트 케이스 수
	int TC;
	cin >> TC;

	for (int tc = 0; tc < TC; tc++) {
		edges.clear();

		cin >> N >> M >> W;

		for (int i = 0; i < M; i++) {
			int S, E, T;
			cin >> S >> E >> T;

			edges.push_back({ S, E, T });
			edges.push_back({ E, S, T });
		}

		for (int i = 0; i < W; i++) {
			int S, E, T;
			cin >> S >> E >> T;

			edges.push_back({ S, E, -T });
		}

		if (bellmanFord(N)) cout << "YES\n";
		else cout << "NO\n";
	}

	return 0;
}

 

4.  유용한 문법 및 알고리즘

4-1) 벨만 포드 알고리즘

// 벨만 코드 알고리즘
bool bellmanFord(int n) {
	// 거리 배열 생성
	vector<int> dist(n + 1, INF);

	// 시작점 거리 0으로 세팅
	dist[1] = 0;

	// 노드의 수 만큼 반복
	for (int i = 0; i < n; i++) {
		// 모든 경로를 탐색하면서 거리 갱신
		for (int pos = 0; pos < edges.size(); pos++) {
			int s = edges[pos].s;
			int e = edges[pos].e;
			int t = edges[pos].t;

			if (dist[s] + t < dist[e]) dist[e] = dist[s] + t;
		}
	}

	// 한번 더 경로 탐색하면서, 거리가 갱신된다면 음수 순환 존재
	for (int pos = 0; pos < edges.size(); pos++) {
		int s = edges[pos].s;
		int e = edges[pos].e;
		int t = edges[pos].t;

		if (dist[e] > dist[s] + t) return true;
	}

	return false;
}