백준 10360번 The Mountain of Gold?



사용한 알고리즘 : 벨만 포드

영어 해석이 굉장히 굉장한 문제였습니다..... ㅎㅎ

T개의 테스트 케이스,

N개의 산, M개의 Ledang Pool 을 주고

(1) 시작점 0으로 다시 돌아갈 수 있는 circle 인지

(2) minuscycle 인지

를 판단하는 문제였습니다.

우선 3중 for 구문으로 벨만 포드를 돌려, minuscycle이 있는지 확인했습니다.

minuscircle이라는 bool 함수를 만들어 minuscycle이 있는경우 그 위치를 true로 체크해 둔 뒤,

isitreturn 이라는 함수를 만들어, minuscircle이 true 인 위치에서 다시 시작점인 0으로 돌아 올 수 있는지 확인해 주었습니다.

	#include <bits/stdc++.h>
	using namespace std;
	#define pii pair<int, int>
	const int INF = 987654321;
	int T,N,M,cnt;
	vector<pii> LedangPool[1000];
	int dist[1000];
	bool minuscircle[1000];
	bool visited[1000];
	bool isitreturn(int x){
	if(visited[x]) return false;
	visited[x] = true;
	for (int i = 0; i < LedangPool[x].size(); ++i){
	int next = LedangPool[x][i].first;
	if(next==0) return true;
	if(isitreturn(next)) return true;
	}
	return false;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> T;
	while(T--){
	cnt++;
	bool returnto0 = false;
	bool MinusCycle = false;
	memset(minuscircle,false,sizeof(minuscircle));
	memset(visited,false,sizeof(visited));
	cin >> N >> M;
	for (int i = 0; i < N; ++i){
	LedangPool[i].clear();
	dist[i] = INF;
	}
	for (int i = 0; i < M; ++i){
	int a, b, c;
	cin >> a >> b >> c;
	LedangPool[a].push_back(pii(b,c));
	}
	dist[0]=0;
	for (int i = 0; i < N; ++i){
	for (int j = 0; j < N; ++j){
	for (int k = 0; k < LedangPool[j].size(); ++k){
	int togo = LedangPool[j][k].first;
	int cost = LedangPool[j][k].second;
	if(dist[j]!=INF && dist[togo] > dist[j]+cost){
	dist[togo] = dist[j]+cost;
	if(i==N-1) {
	MinusCycle = true;
	minuscircle[togo] = true;
	}
	}
	}
	}
	}
	for (int i = 1; i < N; ++i){
	if(minuscircle[i])
	if(isitreturn(i))
	returnto0 = true;
	}
	cout << "Case #" << cnt << ": ";
	if(returnto0 && MinusCycle) cout << "possible" << '\n';
	else cout << "not possible" << '\n';
	}
	return 0;
	}

view raw BOJ 10360.cpp hosted with ❤ by GitHub