[백준 / C++] 11404번: 플로이드 (플로이드 와샬 알고리즘 - Floyd Warshall Algorithm)

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

11404번: 플로이드

난이도: solved.ac 골드 4

 

알고리즘 분류

---

그래프 이론, 플로이드 워셜(Floyd-Warshall)

 

접근 방법

---

플로이드 워셜 (플로이드 와샬) 알고리즘을 그대로 구현하면 되는 문제다

자기 자신으로의 가는 비용은 0으로 두고, 자기 자신을 제외한 나머지 모든 노드로 가는 비용은 INF(가장 큰 수)로 둔다

그리고 점화식을 이용해 다른 노드로 가는데 드는 최소 비용을 계산한다

 

코드

---

#include<iostream>
#include <algorithm>
#define MAX 0x3f3f3f3f
using namespace std;

int dp[101][101];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m, a, b, c;
	int i, j, k;
	cin >> n >> m;

	for (i = 1; i <= n; i++)
		fill(dp[i], dp[i] + n + 1, MAX);
	for (i = 1; i <= n; i++)
		dp[i][i] = 0;

	while (m--) {
		cin >> a >> b >> c;
		dp[a][b] = min(dp[a][b], c);
	}

	for (k = 1; k <= n; k++)
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
	
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			if (dp[i][j] == MAX) {
				cout << "0 ";
			}
			else
				cout << dp[i][j] << " ";
		}
		cout << endl;
	}
}