(백준 1956번 운동) (라이님 블로그 대회 알고리즘 따라잡기 18) 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

최단거리 알고리즘 복습 2탄 - 플로이드 와샬 알고리즘

 

플로이드 와샬 알고리즘이 제일 심플하다..ㅎㅎ

 

백준 1956번

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

 

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int arr[400][400]; 
	int V, E; cin >> V >> E;

	for (int i = 0; i < V; i++) {
		for (int j = 0; j < V; j++) {
			arr[i][j] = INT_MAX;
		}
	}

	for (int i = 0; i < E; i++) {
		int a, b, c; cin >> a >> b >> c;
		arr[a - 1][b - 1] = c;
	}
	
	for (int k = 0; k < V; k++) {
		for (int i = 0; i < V; i++) {
			if (arr[i][k] == INT_MAX) continue;
			for (int j = 0; j < V; j++) {
				if (arr[k][j] != INT_MAX) arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
			}
		}
	}
	int min_dist = INT_MAX;
	for (int i = 0; i < V; i++) {
		if (arr[i][i] != INT_MAX) min_dist = min(arr[i][i], min_dist);
	}

	if (min_dist == INT_MAX) cout << -1;
	else cout << min_dist;

	return 0;
}