[Baekjoon, C++] 1719번 - 택배

 

https://www.acmicpc.net/problem/1719

 

 

 

 

#include <iostream>
#include <climits>
#include <algorithm>



using namespace std;


int main(){
    int n,m;
    cin>>n>>m;


    int d[201][201];
    int num[201][201];

    const int INF = INT_MAX;

    for(int i=1; i<=n; i++){
        fill(d[i], d[i] + n + 1, INF);
        fill(num[i], num[i] + n + 1, 0);
        d[i][i] = 0;
    }





    for(int i=1; i<=m; i++){
        int a,b,c;
        cin>>a>>b>>c;
        if(d[a][b] > c){
            d[a][b] = c;
            d[b][a] = c;
            num[a][b] = b;
            num[b][a] = a;

        }

    }




    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] != INF && d[k][j] != INF && d[i][j] > d[i][k] + d[k][j]){
                    d[i][j] = d[i][k] + d[k][j];
                    num[i][j] = num[i][k];
                    num[j][i] = num[j][k];
                }
            }
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i == j){
                cout<<"- ";
            }
            else{
                cout<<num[i][j]<<" ";
            }
        }
        cout<<'\n';
        
    }








}

 

 

 

2차원 배열을 두 개 선언한다.

d[][] : i에서 j로 이동할 때 걸리는 이동시간 

num[][] : 문제에서 원하는 최단 경로로 갈 때 가장 먼저 가야할 집하장의 번호

 

 

플로이드 워셜을 이용해 한 정점에서 다른 정점으로 이동할 때 드는 비용을 업데이트해나가면서 

최단경로로 갈 때 가장 먼저 가야할 집하장의 번호도 같이 업데이트 하는 것이 포인트다.