11404번 플로이드

 기본적인 플로이드 와샬 문제.

 

 플로이드 와샬을 구현할 수 있으면 그냥 풀 수 있다.

 

 ps. i에서 j로 가는 길이 하나가 아닐 수 있기 때문에 그것만 조심하면 된다(최소값을 찾아서 넣어주면 된다)

 

 

#include <iostream>
#define INF 987654321
#define MAX 101
 
using namespace std;
 
int n,m;
int map[MAX][MAX];
 
void floydWarshall(){
    
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(map[i][k]+map[k][j]<map[i][j]){
                    map[i][j]=map[i][k]+map[k][j];
                }
            }
        }
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(map[i][j]==INF) cout << 0 << " ";
            else cout << map[i][j] << " ";
        }cout << endl;
    }
}
 
int main(){
    cin >> n >> m;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) map[i][j]=0;
            else map[i][j]=INF;
        }
    }
    
    for(int i=0;i<m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        if(map[a][b]!=0){
            map[a][b]=min(c,map[a][b]);
        }
        else{
            map[a][b]=c;
        }
    }
    
    floydWarshall();
}