[BOJ] 플로이드

[BOJ] 플로이드

Problem URL : 플로이드

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

using namespace std;

int dist[101][101];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m;
	cin >> n >> m;
	fill(&dist[0][0], &dist[n][n], INF);
	
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		dist[a][b] = min(dist[a][b], c);
	}
	for (int i = 1; i <= n; i++) {
		dist[i][i] = 0;
	}

	// for 문 순서에 주의하자
	// 하나의 mid 포인트씩 중심으로 해서 최신화를 시켜야 한다.
	// mid 값 for문이 안쪽에 있으면 순서에 따라 최신화가 불가능한 경우가 생긴다
	for (int mid = 1; mid <= n; mid++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (dist[i][mid] != INF && dist[mid][j] != INF) {
					dist[i][j] = min(dist[i][mid] + dist[mid][j], dist[i][j]);
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dist[i][j] == INF) dist[i][j] = 0;
			cout << dist[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}