[백준] 11404번 플로이드

그 유명한 플로이드(Floyd) 알고리즘이다.

11404번: 플로이드

주의할 점은 n에서 m으로 가는 이음선이 여러 개가 있을 수 있다는 것이다. 따라서 가중치를 입력받을 때 작은 값만 배열에 저장하도록 해야 한다.

플로이드 알고리즘은 아래 글에서 자세히 설명해놓았다.

https://breakcoding.tistory.com/148

[알고리즘] 플로이드 (Floyd) 알고리즘

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n, e;
	cin >> n >> e;
	const int INF = 100001;
	vector<vector<int>> d(n + 1, vector<int>(n + 1, INF));
	for (int i = 1; i <= n; i++) {
		d[i][i] = 0;
	}
	for (int i = 0; i < e; i++) {
		int from, to, weight;
		cin >> from >> to >> weight;
		if(d[from][to] == 0 || d[from][to] == INF)
			d[from][to] = weight;
		else d[from][to] = min(weight, d[from][to]);
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (d[i][j] == INF) cout << 0 << " ";
			else cout << d[i][j] << " ";
		}
		cout << '\n';
	}
	return 0;
}