운동 (feat. 백준, 1956번)

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

1956번: 운동

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <algorithm>
using namespace std;
int V, E;
int arr[401][401];
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> V >> E;
	for (register int i = 1, j; i <= V; ++i)
		for(j = 1; j <= V; ++j)
			arr[i][j] = static_cast<int>(1e9);
	for (register int e = 0, a, b, c; e < E; ++e)
		cin >> a >> b >> c, arr[a][b] = c;
	for (register int m = 1, f, t; m <= V; ++m)
		for (f = 1; f <= V; ++f)
			for (t = 1; t <= V; ++t)
				arr[f][t] = min(arr[f][t], arr[f][m] + arr[m][t]);
	register int ans = static_cast<int>(1e9);
	for(register int i = 1, j; i <= V; ++i)
		for(j = 1; j <= V; ++j)
			ans = min(ans, arr[i][j] + arr[j][i]);
	if (ans == static_cast<int>(1e9))
		cout << -1;
	else
		cout << ans;
	return 0;
}
// *&)*@*

이전 '플로이드' 문제와 같은 워셜 알고리즘 풀이법입니다.

방식은 3중 for문으로 정형화된 형태이므로 아래를 참고하세요.

플로이드 (feat. 백준, 11404번)