[백준 / C++] 1956번: 운동 (플로이드 워셜 알고리즘)

https://www.acmicpc.net/problem/1956

1956번: 운동

 

난이도: solved.ac 골드 4

 

알고리즘 분류

---

그래프 이론, 플로이드 워셜 (Floyd-Warshall)

 

접근 방법

---

다익스트라 알고리즘을 이용할 수도 있겠지만 정점의 개수가 적으므로 플로이드 워셜 알고리즘을 이용하였다.

 

구현

---

기존의 플로이드 워셜 문제에서는 자기 자신으로 가는 비용은 0으로 초기화했지만, 이 문제에서는 자기 자신을 포함한 모든 노드로 가는 비용을 가장 큰 수로 초기화 했다.

그리고 플로이드 워셜 알고리즘을 이용해 점화식으로 각 노드로의 최소 비용을 계산한다.

V^3번의 연산을 모두 하고 난 뒤에는 자기 자신으로 가는 최소 비용을 찾아 출력한다.

 

코드

---

#include<iostream>
#include <algorithm>
#define MAX 0x3f3f3f3f

using namespace std;
int village[401][401];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int V, E, i, j, k;
	cin >> V >> E;
	for (i = 1; i <= V; i++)
		fill(village[i] + 1, village[i] + V + 1, MAX);

	int a, b, c;
	while (E--) {
		cin >> a >> b >> c;
		village[a][b] = c;
	}
	for (k = 1; k <= V; k++) {
		for (i = 1; i <= V; i++) {
			for (j = 1; j <= V; j++) {
				village[i][j] = min(village[i][j], village[i][k] + village[k][j]);
			}
		}
	}
	int min = MAX;
	for (i = 1; i <= V; i++) {
		if (village[i][i] < min)
			min = village[i][i];
	}
	if (min == MAX)
		cout << -1;
	else
		cout << min;
}