Boj 11404 c++ 플로이드 워셜

모든 지점에서 모든 지점까지의 최단경로를 구하는 알고리즘. 삼중for문과 초기값 설정을 이용해서 풀이할 수 있다.

동일지점까지의 거리는 항상 0임에 유의.

#include<iostream>
#define Max 1000000001
using namespace std;
int n, m;
int mp[101][101];

int main(){
    cin>>n>>m;
    int a, b, v;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            mp[i][j]=Max;
            if(i==j){
                mp[i][i]=0;
            }
        }
    }
    for(int i=0; i<m; i++){
        cin>>a>>b>>v;
        if(mp[a][b]>v){
            mp[a][b]=v;
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int k=1; k<=n; k++){
                mp[j][k]=min(mp[j][k], mp[j][i]+mp[i][k]);
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
                if(mp[i][j]==Max){
                    cout<<"0"<<" ";
                }
                else{
                    cout<<mp[i][j]<<" ";
                }
        } cout<<"\n";
    }
}