[백준 1956] 운동 (C++)

이 문제는 도로의 길이의 합이 가장 작은 사이클을 찾는 문제이다. 이때, 사이클을 이루는 도로의 길이 합이 최소가 되려면 도로의 길이 자체가 최소가 되어야 한다. 따라서, 각 정점사이의 최단 경로를 구해야하므로 플로이드 워셜 알고리즘으로 접근해야 한다.

그런데, 이 문제에서는 사이클을 이루는 도로의 길이 합이 최소가 되도록 해야한다. 즉, 시작점 $S$와 끝점 $E$가 존재할 때, $S$에서 $E$로 최단 경로로 갔다가 $E$에서 $S$로 최단경로로 되돌아와야한다. 따라서, 해당 값은 w[s][e] + w[e][s]가 됨을 알 수 있다.

시간 복잡도를 고려해 보면, 입력이 $O(V + E)$이고, 플로이드 워셜 알고리즘이 $O(V^3)$, 답을 구하는 과정이 $O(V^2)$이므로 전체 시간 복잡도는 $O(V^3)$으로 시간 내에 답을 구할 수 있다.

그리고, 거리가 $10,000$이하이고 정점 개수가 $400$이하이므로 최악의 경우 두 정점 사이의 거리는 $4 \times 10^6$가 되기 때문에 이보다 큰 $10^7$으로 INF를 설정해주면 될 것이다.

이를 바탕으로 코드를 작성하면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e7;
int v, e, ans = INF;
int w[401][401];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	// 입력
	cin >> v >> e;
	for (int i = 1; i <= v; i++) {
		fill(w[i], w[i] + v + 1, INF);
		w[i][i] = 0;
	}
	for (int i = 0, a, b, c; i < e; i++) {
		cin >> a >> b >> c;
		w[a][b] = min(w[a][b], c);
	}

	// 플로이드 => 최단 경로
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
			}
		}
	}

	// 최소인 왕복 거리 구하기
	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= v; j++) {
			if (i == j || w[i][j] + w[j][i] > INF) continue;
			ans = min(ans, w[i][j] + w[j][i]);
		}
	}

	if (ans == INF) cout << -1;
	else cout << ans;
}