백준 11404 플로이드

// 25분
 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;
 
const int INF = 1000000000;
 
int main() {
    int n, m, dist[100][100];
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dist[i][j] = (i == j ? 0 : INF);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        dist[a - 1][b - 1] = min(dist[a - 1][b - 1], c);
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INF) dist[i][j] = 0;
            printf("%d ", dist[i][j]);
        }
        puts("");
    }
    return 0;
}
 

처음으로 풀어 본 플로이드-와샬 알고리즘

주의할 점은 배열의 인덱스를 0부터 시작한다는 것과

27번줄의 if (dist[i][j] == INF) dist[i][j] = 0; 

 "만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다."

라는 조건을 놓치지 말 것.