플로이드-와샬 알고리즘 [Floyd-Warshall Algorithim]

Floyd-Warshall

---

Link

11404번 : 플로이드

#include <iostream>
using namespace std;
int dp[100][100];
const int INF = 1e9;

int main(){
    int N, M; cin >> N >> M;
    for(int i=0; i<N; ++i){
        for(int j=0; j<M; ++j){
            dp[i][j] = INF;
        }
        dp[i][i] = 0;
    }
    // 초기화 : 자기 자신은 0, 나머지는 INF(무한)
    
    
    // 입력단계에서 dp[i][j] : i에서 j까지의 거리
    for(int i=0; i<M; ++i){
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        dp[u][v] = min(dp[u][v], w);
    }

    for(int k=0; k<N; ++k){
        for(int i=0; i<N; ++i){
            for(int j=0; j<N; ++j){
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
    // dp갱신 후 dp[i][j] : i에서 j까지의 최단거리

    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            if(dp[i][j] == INF) cout << 0 << ' ';
            else cout << dp[i][j] << ' ';
        }
        cout << '\n';
    }
}

---