记录编号	462125	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	ユッキー	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2017-10-21 11:00:33	内存使用	0.44 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define MAXN 105
#define MAXW 10000000
int G[MAXN][MAXN];
int P[MAXN][MAXN];
int N[MAXN][MAXN];
void walk(int s,int e)
{
    if(s==e)return;
    printf("%d ",s);
    if(G[s][N[s][e]]==MAXW)
        walk(N[s][N[s][e]],N[s][e]);
    walk(N[s][e],e);
}
int main()
{
    int n,m,v,x,y;
    int i,j,k;
freopen("djs.in","r",stdin);
freopen("djs.out","w",stdout);
    scanf("%d%d%d",&n,&m,&v);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)G[i][j]=MAXW;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)N[i][j]=j;

    for(i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        scanf("%d",&G[x][y]);
    }
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)P[i][j]=G[i][j];

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            for(k=0;k<n;k++)
                if(P[i][k]+P[k][j]<P[i][j])
                {
                    P[i][j]=P[i][k]+P[k][j];
                    N[i][j]=k;
                }

    for(i=0;i<n;i++)
    {
        printf("%d:\n",i);
        if(P[v][i]==MAXW || i==v)printf("no\n");
        else
        {
            printf("path:");
            walk(v,i);
            printf("%d\ncost:%d\n",i,P[v][i]);
        }
    }
    return 0;
}