Baekjoon 11404 (플로이드)

Baekjoon 11404, 백준 11404 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기

#include <cstdio>
#include <algorithm>
#define INF 999999999

using namespace std;

int n, m;
int dp[102][102];  // initial: dp[from][to] = value

void Floyd_Warshall() {
    // consider passing node 'temp'
    for(int temp = 1; temp <= n; temp++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(dp[i][temp] != INF && dp[temp][j] != INF){
                    dp[i][j] = min(dp[i][j], dp[i][temp] + dp[temp][j]);
                }
            }
        }
    }
}

int main() {

    // put inputs & initalization
    scanf("%d", &n);
    scanf("%d", &m);

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

    while(m--){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);

        if(dp[a][b] > c)
            dp[a][b] = c;
    }

    // Solution by Floyd-Warshall Algorithm
    Floyd_Warshall();

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(dp[i][j] == INF || i == j) printf("0 ");
            else printf("%d ", dp[i][j]);
        }

        printf("\n");
    }
}

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 의 기본적인 구현이다!

알고리즘에 대한 이론은 여기에서 확인할 수 있다.