1719번 택배

 알고리즘 분류에는 다익스트라로 되어있지만 모든 정점에서 모든 정점으로 가는 경로를 구해야하므로 플로이드 와샬로 풀었다.

 

 

#include <iostream>
#define INF 987654321
#define MAX 201
 
using namespace std;
 
int n,m;
int V[MAX][MAX];
int map[MAX][MAX];
 
void solved(){
    int d[MAX][MAX];
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            d[i][j]=V[i][j];
        }
    }
    
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(d[i][k]+d[k][j]<d[i][j]){
                    d[i][j]=d[i][k]+d[k][j];
                    map[i][j]=map[i][k];
                }
            }
        }
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(map[i][j]==0) cout << "-" << " ";
            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) V[i][j]=0;
            else V[i][j]=INF;
        }
    }
    
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        V[a][b]=c;
        V[b][a]=c;
        map[a][b]=b;
        map[b][a]=a;
    }
    
    solved();
}