[C++] 백준 11404번 - 플로이드

이름에서도 유추할 수 있듯이 플로이드 와샬 알고리즘을 쓰면 된다

 

#include <bits/stdc++.h>
#define endl '\n'

#define INF 987654321
using namespace std;

int table[101][101];
int n, m;
int a, b, c;

void FloydFunction(int n) {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (table[i][k] != INF || table[k][j] != INF)
                    table[i][j] = min(table[i][j], table[i][k] + table[k][j]);
            }
        }
    }
}


int main() {

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    cin >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            table[i][j] = INF;
        }
    }

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

    FloydFunction(n);
  
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (table[i][j] == INF || i == j) cout << "0 ";
            else cout << table[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}