记录编号	206240	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	NVIDIA	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2015-11-06 12:04:40	内存使用	0.41 MiB

#include<bits/stdc++.h>
#define inf 999999999
int i,j,k,n,m,v,a1,b1,c1,temp,path,cost,b[10010],pr[10010],up[10010],a[100][100];
void DO(int v1) 
{
    int temp;
    temp=up[v1];
    if(temp!=0)
	DO(temp);
    if(v1!=v)
	printf("%d ",v1);
}
int main() 
{
    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++)
		if(i==j)a[i][j]=0;
			else a[i][j]=inf;
   
    for(i=1;i<=m;i++) 
	{
        scanf("%d%d%d",&a1,&b1,&c1);
        a[a1][b1]=c1;//有向图
        pr[i]=up[i]=0;//标记初始
        b[i]=inf;
    }
    pr[0]=0;
    b[0]=inf;
    b[v]=up[0]=0;
    for(k=0;k<n;k++) 
	{
        temp=inf;
        for(i=0;i<n;i++)
            if(pr[i]==0&&b[i]< temp)
                temp=b[j=i];
        pr[j]= 1;
        for(i=0; i<n; i++)
            if(a[j][i]!=inf)
                if(a[j][i]+b[j]< b[i]) 
				{
                    b[i]=a[j][i]+b[j];
                    up[i]=j;
                }
    }
    for(i=0;i<n;i++) 
	{
        printf("%d:\n",i);
        if(i==v||b[i]==inf)
            printf("no\n");
        else 
		{
            printf("path:%d ",v);
            DO(up[i]);
            printf("%d\n",i);
            printf("cost:%d\n",b[i]);
        }
    }
    return 0;
}