백준 11404 : 플로이드

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

제목부터 플로이드다

플로이드-와샬 알고리즘을 알고있다면 그냥 n^3 한다음에

2차원배열을 출력하면 끝.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include <iostream> #define MAX 101 #define INF 1000000000 using namespace std; int matrix[MAX][MAX]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ matrix[i][j] = (i==j) ? 0:INF; } } while(m--){ int a, b, w; cin >> a >> b >> w; if(matrix[a][b] > w){ matrix[a][b] = w; } } for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(matrix[i][j] > matrix[i][k] + matrix[k][j]){ matrix[i][j] = matrix[i][k] + matrix[k][j]; } } } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(matrix[i][j] == INF) matrix[i][j] = 0; cout << matrix[i][j] << " "; } cout << '\n'; } return 0; }