[백준] 11404번 플로이드 C++ 문제풀이

https://www.acmicpc.net/problem/11404

11404번: 플로이드

문제 풀이

이 문제는 플로이드 워셜 알고리즘을 통해 두 도시 사이의 최소 비용을 구하는 문제다

플로이드 워셜 알고리즘은 모든 정점들간의 최단 거리를 계산하는 알고리즘으로, 시간복잡도는 O(N^3)이다.

i 와 j 두 정점 사이의 거리를 구할 때 k를 중간에 거쳐서 가는 것이 더 짧으면 갱신하면 된다.

소스 코드

#include <iostream>
using namespace std;

int dp[101][101] = { 0 };

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i != j) {
				dp[i][j] = 10000001;
			}
		}
	}
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		dp[a][b] = min(dp[a][b], c);
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (dp[i][k] + dp[k][j] < dp[i][j]) {
					dp[i][j] = dp[i][k] + dp[k][j];
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dp[i][j] == 10000001) {
				cout << "0" << " ";
			}
			else
				cout << dp[i][j] << " ";
		}
		cout << '\n';
	}
}