[C/C++] 백준 1865번 - 웜홀

✏️ 문제 링크

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

1865번: 웜홀

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

일반적으로 벨만-포드 알고리즘은 방문하는 노드의 거리배열값이 MAX라면 무시하고 지나가지만

이 문제의 경우에는 틀리게 됩니다. 자세한 내용은 아래 링크를 타고 들어가시면 될 것 같습니다.

시작점부터 도착점까지의 거리가 MAX가 아닌 dist[i]의 값이 i를 방문하지 않았다~라는 의미로 해석해야 됩니다

https://www.acmicpc.net/board/view/72951

글 읽기 - 1865번 빠진 조건 추가 요청입니다

 

✏️ 문제 코드

#include<iostream>
#include<tuple>
#include<vector>
#include<limits.h>
using namespace std;

typedef tuple<int, int, int>edge;
vector<long>dist;
bool time_travel(int n, vector<edge>edges);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	cin >> T;

	for (int x = 0; x < T; x++) {

		vector<edge>tree;
		int N, M, W;
		cin >> N >> M >> W;

		dist.resize(N + 1);	
		fill(dist.begin(), dist.end(), INT_MAX);

		for (int i = 0; i < M; i++) {
			int start, end, time;
			cin >> start >> end >> time;
			tree.push_back(edge(start, end, time));
			tree.push_back(edge(end, start, time));
		}

		for (int i = 0; i < W; i++) {
			int start, end, time;
			cin >> start >> end >> time;
			tree.push_back(edge(start,end, -time));
		}

		dist[1] = 0;
		bool iscycle = time_travel(N, tree);

		if (iscycle)
			cout << "YES" << "\n";
		else
			cout << "NO" << "\n";	
	}
}
bool time_travel(int n,vector<edge>tree) {

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < tree.size(); j++) {
			edge edges = tree[j];
			int start = get<0>(edges);
			int end = get<1>(edges);
			int time = get<2>(edges);
			if (dist[end] > dist[start] + time) {
				dist[end] = dist[start] + time;
			}
		}
	}

	for (int j = 0; j < tree.size(); j++) {
		edge edges = tree[j];
		int start = get<0>(edges);
		int end = get<1>(edges);
		int time = get<2>(edges);
		if (dist[end] > dist[start] + time) {
			return true;
		}
	}
	return false;
}