11780 플로이드 2

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

플로이드 와샬(Floyd-Warshall) 알고리즘은 그래프의 모든 정점 사이의 최단 거리를 O(N^3)에 구하는 알고리즘이다. 다이나믹 프로그래밍으로 접근하여 특정 정점 사이에 모든 경유지에 대해서 최단 거리를 갱신하면서 테이블을 채워 나간다. 이 문제는 최단 거리 + 경로까지 구하는 문제이다. 다음의 정점을 나타내는 path를 두고 i->k->j 에서 매번 경유지가 갱신될 때마다 다음정점이 k로 바뀌므로 path[i][j]를 path[i][k]로 바꿔준다.

#include <cstdio>
#include <vector>
#define INF 987654321
using namespace std;
 
int n,m,a,b,c,d[101][101],path[101][101];
void print(int i,int j)
{
    if(d[i][j]==0 || d[i][j]==INF)
    {
        printf("0\n");
        return;
    }
    vector<int> p;
    p.push_back(i);
    while(i!=j)
    {
        p.push_back(path[i][j]);
        i=path[i][j];
    }
    int size=p.size();
    printf("%d ",size);
    for(int i=0;i<size;i++)
        printf("%d ",p[i]);
    printf("\n");
}
 
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
        (i==j)?d[i][j]=0:d[i][j]=INF;
    while(m--)
    {
        scanf("%d %d %d",&a,&b,&c);
        if(d[a][b]>c) d[a][b]=c,path[a][b]=b;
    }
    for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
        if(d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j],path[i][j]=path[i][k];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            printf("%d ",d[i][j]!=INF?d[i][j]:0);
        printf("\n");
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) print(i,j);
    return 0;
}