[백준 11404번] 플로이드(C++)

아이디어

플로이드 와샬 알고리즘 사용.

동빈나 센세의 글보고 이해하자.

24. 플로이드 와샬(Floyd Warshall) 알고리즘

 

C++풀이

#include <bits/stdc++.h>

using namespace std;
int n, m;
int board[101][101];
void floyd(){
    //플로이드는 중간에 거쳐가는것이 핵심이다.
    for(int k = 1 ; k<=n; k++)
    {
        for(int i = 1 ; i<=n; i++)
        {
            for(int j = 1 ; j<=n; j++)
            {
                //거쳐가는것이 그냥 가는것 보다 짧다면 갱신
                if(board[i][j] > board[i][k]+ board[k][j]) 
                {
                    board[i][j] = board[i][k] + board[k][j];
                }
            }
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    memset(board,0x1f,sizeof(board));
    for(int i = 0 ; i< m; i++)
    {
        int s, e, w;
        cin >> s >> e >> w;
        if(board[s][e] > w){
            board[s][e] = w;
        }
    }
    for(int i = 1 ; i<=n; i++)
    {
        board[i][i] = 0;
    }
    floyd();
    for(int i = 1 ; i<= n ; i++)
    {
        for(int j = 1 ; j<= n; j++)
        {
            if(board[i][j] <10000000) cout << board[i][j] << " ";
            else cout << 0 << " ";
        }
        cout << endl;
    }
}