[백준 11404] 플로이드 (C++)

이 문제는 모든 정점에 대해 다른 정점으로의 최소 비용을 구하는 문제이다. 즉, 플로이드 워셜을 통해 문제를 해결할 수 있다.

플로이드 워셜 알고리즘은 그래프가 주어져있을 때, 정점 s에서 정점 t로의 최소 비용 d[s][t]는 min(d[s][t], d[s][k] + d[k][t])가 됨을 이용하여, d[s][t]를 구하는 알고리즘이다.
즉, 임의의 정점 s, t, k가 존재할 때, s에서 t로의 최소 비용은 s에서 t로 곧바로 가는 것과 k를 거쳐가는 것 중 비용이 더 작은 것들을 선택해나가면 된다는 아이디어이다.

이 때, s에서 t로의 최소 비용 d[s][t]가 정말 최소 비용임을 보장하려면, 중간 노드를 먼저 고정하고 시작점과 도착점에 대한 최소 비용을 구해나가야 최소 비용을 빠짐없이 구할 수 있음을 유의하자.

이를 코드로 옮기면 다음과 같아진다.

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
int n, m;
int d[101][101];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 101; i++) {
		fill(d[i], d[i] + 101, INF);
		d[i][i] = 0;
	}

	cin >> n >> m;
	for (int i = 0, a, b, c; i < m; i++) {
		cin >> a >> b >> c;
		d[a][b] = min(d[a][b], c);
	}

	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";
	}
}

시간복잡도는 $O(V^3)$으로 AC를 받을 수 있다.