11404번 플로이드

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

백준 boj 플로이드 와샬 최단거리

36, 50번 째 줄 주석문만 참고.

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 111
#define INF 2e9
 
int fw[Max][Max], n, m;
 
int main()
{
    cin.tie(0);
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            fw[i][j] = i == j ? 0 : INF;
        }
    }
 
    int f, t, c;
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &f, &t, &c);
        if (fw[f][t] == INF) {
            fw[f][t] = c;
        }
        else {
            fw[f][t] = min(fw[f][t], c);
        }
    }
    
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                /*
                i → k 또는 k → j 버스 노선이 없는 경우도 무시해야 한다.
                */
                if (i == j || fw[i][k] == INF || fw[k][j] == INF) {
                    continue;
                }
                if (fw[i][j] > fw[i][k] + fw[k][j]) {
                    fw[i][j] = fw[i][k] + fw[k][j];
                }
            }
        }
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            // i → j 못 가는 경우는 0 출력.
            printf("%d ", fw[i][j] == INF ? 0 : fw[i][j]);
        }
        printf("\n");
    }
 
    return 0;
}