[BOJ/백준][Gold4] 11780 : 플로이드2 (C++)

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

11780번: 플로이드 2

 

 

[난이도] Gold4
[유형] 플로이드 와샬

[풀이]
플로이드 와샬의 경로까지 출력해야 하는 문제이다.
최단경로를 갱신할 때 경유지 i,j의 경유지 k를 path[i][j]에 저장해놓고
이것을 이용해 재귀함수로 경로를 출력한다.

 

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int N,M,dist[101][101],path[101][101],INF=9e8;
void prt(int i,int j,vector<int>& tmp){
    if(i==j) {
        tmp.push_back(i);
        return;
    }
    int p = path[i][j];
    prt(i,p,tmp);
    if(i!=p) prt(p,j,tmp);
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) if(i!=j) dist[i][j]=INF;  
             
    while(M--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(dist[a][b] > c){
           dist[a][b] = c;
           path[a][b] = 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];
                   path[i][j]=k;
                }
            }
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)
            printf("%d ",dist[i][j]==INF ? 0 : dist[i][j]);
        puts("");
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(!dist[i][j]) printf("0");
            else {
                vector<int> tmp;
                prt(i,j,tmp);
                tmp.push_back(j);
                printf("%d ",tmp.size());
                for(auto k : tmp) printf("%d ",k);
            }
            puts("");
        }
    }
}

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