Boj11404_플로이드

Published: December 09, 2018 by 아형

• Categories:
• Algorithm 74

• Tags:
• 알고리즘 72

boj11404_플로이드

#include<iostream>
#include<algorithm>
using namespace std;
int arr[110][110], n, m, start, finish, weight;
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			if (i == j) arr[i][j] = 0;
			else arr[i][j] = 1e9;
		}
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &start, &finish, &weight);
		arr[start][finish] = min(arr[start][finish], weight);
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j] == 1e9) printf("0 ");
			else printf("%d ", arr[i][j]);
		}
		printf("\n");
	}
}