백준 1956번 운동

문제링크

문제 해설

접근법

마을간의 도로는 일방 통행이다. 방향과 가중치가 있는 그래프이다.

문제를 더 작게 나누어보면 a에서 b를 가고 b에서 a를 올 수 있냐는 것이다.

또한, 그 중 최소 사이클의 도로 길이의 합을 구해야하므로 모든 마을을 확인해야 한다.

모든 마을에서 모든 마을까지 갈 수 있는 지 확인하는 방법, 익숙하다

바로, 플로이드 와샬 알고리즘이다.

플로이드 와샬 알고리즘을 통해 정점 간의 거리를 구한다.

그런 후 a -> b -> a의 거리의 합을 구하면 된다.

풀이

특별한 건 없다. 플로이드 와샬 알고리즘을 사용한다.

거리를 저장한 배열이 map이라고 한다면

map[a][b] + map[b][a]를 구하면 된다.

소스코드

#include <iostream>
#include <climits>
#include <algorithm>

using namespace std;

int map[401][401];
int v, e;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> v >> e;
    
    // 무한으로 초기화
	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= v; j++) {
			if (i == j) map[i][j] = 0;
			else map[i][j] = INT_MAX;
		}
	}

	for (int i = 0; i < e; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		map[a][b] = min(map[a][b], c);
	}
	// 정점 간의 거리 계산
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				if (map[i][k] == INT_MAX || map[k][j] == INT_MAX) continue;
				map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
			}
		}
	}

	int answer = INT_MAX;
	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= v; j++) {
            // 최소 사이클 거리 계산
			if (i==j || map[i][j] == INT_MAX || map[j][i] == INT_MAX) continue;
			answer = min(answer, map[i][j] + map[j][i]);
		}
	}

	if (answer == INT_MAX) 
		cout << "-1";
	else {
		cout << answer;
	}

	
	return 0;
}