记录编号	348719	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	Zwoi_John Price	是否通过	通过
代码语言	C	运行时间	0.004 s
提交时间	2016-11-14 15:43:04	内存使用	0.33 MiB

#include<stdio.h>
int path[101]={0},mp[101][101]={0},inf=99999999,dis[101],m,n,v;
void find(int x)
{
	if (x==v) printf("%d ",x);
	else
	{
		find(path[x]);
		printf("%d ",x);
	}
}
int main()
{
	int i,min,k,k1,j,mk[101]={0},t2,t1,t3;
	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++)
		{
			mp[i][j]=inf;
		}
	}
	for (i=1;i<=m;i++)
	{
		scanf("%d %d %d",&t1,&t2,&t3);
		mp[t1][t2]=t3;
	}
	for (i=0;i<n;i++) dis[i]=inf;
	dis[v]=0;
	
	for (i=0;i<=n-1;i++)
	{
		min=inf+1;
		for (j=0;j<n;j++)
		{
			if ((mk[j]!=1)&&(dis[j]<min))
			{
				min=dis[j];
				k=j;
			}
		}
		mk[k]=1;
		for (k1=0;k1<n;k1++)
		{
			if ((mp[k][k1]+dis[k]<dis[k1])&&(k!=k1))
			{
				dis[k1]=mp[k][k1]+dis[k];
				path[k1]=k;
			}
			
		}
	}
	for (i=0;i<n;i++)
	{
		printf("%d:\n",i);
		if ((i==v)||(dis[i]==inf)) printf("no\n");
		else
		{
			printf("path:");
			find(i);
			printf("\n");
			printf("cost:%d\n",dis[i]);
		}
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}