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

플로이드
https://www.acmicpc.net/problem/11404

11404번: 플로이드

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
int ans[101][101];
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N >> M;
	for (register int i = 1, j; i <= N; ++i)
		for (j = 1; j <= N; ++j)
			ans[i][j] = static_cast<int>(1e9);
	for (register int i = 1; i <= N; ++i)
		ans[i][i] = 0;
	for (register int m = 0, x, y, c; m < M; ++m)
		cin >> x >> y >> c, ans[x][y] = min(ans[x][y], c);
	for (register int m = 1, f, t; m <= N; ++m)		// mid
		for (f = 1; f <= N; ++f)			// from
			for (t = 1; t <= N; ++t)		// to
				ans[f][t] = min(ans[f][t], ans[f][m] + ans[m][t]);
	for (register int i = 1, j; i <= N; ++i) {
		for (j = 1; j <= N; ++j)
			if (ans[i][j] == static_cast<int>(1e9))
				cout << "0 ";
			else
				cout << ans[i][j] << " ";
		cout << "\n";
	}
	return 0;
}
// *&)*@*

1. 2중 for문을 통해 구할 수 있는 문제입니다.
2. 하지만 문제에서 요구하는 워셜 알고리즘을 사용하였습니다.
3. 워셜 알고리즘은 A에서 B를 거친 뒤 C로 가는 그래프 탐색에 적합합니다. 3중 for문으로 정형화된 방식입니다.