백준 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;
}