[백준] 플로이드 11404번 (c++)

출처 : 11404번: 플로이드 (acmicpc.net)

11404번: 플로이드

풀이 방법

플로이드 와샬 알고리즘을 사용하면 된다.

#include <bits/stdc++.h>
using namespace std;

int INF = 987654321;
int n, m, s, e, w;
int edge[101][101];

void floyd() {
    for (int i = 1;i <= n;i++) { // 거쳐 가는 노드
        for (int j = 1;j <= n;j++) { // 시작 노드
            for (int k = 1;k <= n;k++) { // 도착 노드
                edge[j][k] = min(edge[j][k], edge[j][i] + edge[i][k]);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) { // 최댓값으로 초기화
        for (int k = 1;k <= n;k++) {
            edge[i][k] = INF;
        }
    }
    for (int i = 0;i < m;i++) {
        cin >> s >> e >> w;
        if (edge[s][e] > w) {
            edge[s][e] = w;
        }
    }
    floyd();
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (edge[i][j] >= INF || i == j) {
                cout << 0 << " ";
            }
            else {
                cout << edge[i][j] << " ";
            }
        }
        cout << endl;
    }
    return 0;
}