BOJ - 1956번 운동(C++)

문제 출처: https://www.acmicpc.net/problem/1956

문제 난이도

Gold 4

문제 접근법

사이클을 발견해서 최소 거리 비용을 구하는 문제.
다익스트라나 프림은 사이클이 없을 경우에 이용가능하니깐 그냥 우선순위큐만 응용해서 구하려했으나 틀렸습니다 떴다.
알고보니 플로이드-와샬을 이용한다. 음의 사이클이 없으면 되는 것 + 중간에 들려서 목적지에 도착하는 것 + N값이 적은것 = 플-와

통과 코드

#include <iostream>
#include <algorithm>
#define INF 4001234

using namespace std;

int arr[401][401];

int main() {
	int V, E;
	cin >> V >> E;
	for (int i = 1; i <= V; i++) {
		for (int j = 1; j <= V; j++) {
			arr[i][j] = INF;
		}
	}
	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		arr[a][b] = c;
	}
	int ans = INF;
	for (int k = 1; k <= V; k++) {
		for (int i = 1; i <= V; i++) {
			for (int j = 1; j <= V; j++) {
				if (arr[i][k] + arr[k][j] < arr[i][j]) {
					arr[i][j] = arr[i][k] + arr[k][j];
				}
			}
		}
	}
	for (int i = 1; i <= V; i++) {
		for (int j = 1; j <= V; j++) {
			if (i == j) continue;
			ans = min(ans, arr[i][j]+ arr[j][i]);
		}
	}
	ans = ans == INF ? -1 : ans;
	cout << ans << "\n";

	return 0;
}

피드백

플로이드 와샬을 이용할 줄은 몰랐다.. 의외 다시 본인으로 되돌아오는 경로에 이 알고리즘을 쓸 수 있다는 걸 기억해놔야겠다.