[DP] 플로이드 워셜 최단거리

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

#include <iostream>
using namespace std;

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    // init
    int arr[n][n];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if( i == j ) arr[i][j] = 0;
            else arr[i][j] = -1;
            
        }
    }
    
    // input
    for (int i = 0; i < m; ++i) {
        int row, col, weight;
        cin >> row >> col >> weight;
        
        if( arr[row - 1][col - 1] < 0 || arr[row - 1][col - 1] > weight ){
            arr[row - 1][col - 1] = weight;
        }
    }
    
    for (int k = 0; k < n; ++k) {
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; ++i) {
                if( arr[i][k] == -1 || arr[k][j] == -1 ) continue;
                if(  arr[i][k] + arr[k][j] < arr[i][j] || arr[i][j] == -1 ) {
                    arr[i][j] = arr[i][k] + arr[k][j];
                }
            }
        }
    }
    
    
    for (int i = 0; i < n; ++i) {
        if( i > 0 ) cout << '\n';
        for (int j = 0; j < n; ++j) {
            if( arr[i][j] == - 1 ) arr[i][j] = 0;
            if( j > 0 ) cout << " ";
            cout << arr[i][j];
        }
    }
    
    return 0;
}

모든 노드 간 최단 경로 구하기

중간 노드를 설정함 (k)

-1이면 거리가 무한