[BOJ/백준][Gold4] 1719 : 택배 (C++)

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

1719번: 택배

 

 

[난이도] Gold4
[유형] 플로이드 워셜

[풀이]
각 집하장간 최단거리는 플로이드 워셜 알고리즘으로 구할 수 있다.
이 문제에서는 플로이드로 i,j의 최단 경로를 구했을 때, i다음 가야하는
집하장을 구해야한다. 이것을 path[i][j]에 저장한다.
경로를 갱신할 때 다음 중간에 거쳐가야할 집하장을 k라고 하면
path[i][j] = path[i][k]로 갱신하여 모든 i,j 쌍에 대해 path[i][j]를 구할 수 있다.

 

#include <cstdio>
int N,M,dist[201][201],inf=9e8,path[201][201];
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) {
            dist[i][j]=inf;
            if(i==j) dist[i][j]=0;
        }
    while(M--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        dist[a][b]=dist[b][a]=c;
        path[a][b]=b;
        path[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(dist[i][j] > dist[i][k]+dist[k][j]){
                   dist[i][j] = dist[i][k]+dist[k][j];
                   if(i!=k) path[i][j] = path[i][k];
                }
            }    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++) {
            if(path[i][j]) printf("%d ",path[i][j]);
            else printf("%c ",'-');
        }        
        puts("");
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1719.cpp