记录编号	349212	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	ZWOI_Love_/幻想	是否通过	通过
代码语言	C	运行时间	0.004 s
提交时间	2016-11-14 20:23:20	内存使用	0.38 MiB

#include<stdio.h>
#include<stdlib.h>

int p[101][101],dis[101],e[101][101],book[101],pa[101],i,j,o,u,v,m,n,t1,t2,t3,min;
int inf=99999999;
char r[101][101];


int main()
{
	freopen("djs.in","r",stdin);
	freopen("djs.out","w",stdout);
	scanf("%d %d %d\n",&n,&m,&o);
	
	
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			p[i][j]=inf;
			if(i==j) e[i][j]=0;
		    else e[i][j]=inf;
		}
	
	for(i=0;i<m;i++)
	{
		scanf("%d %d %d\n",&t1,&t2,&t3);
		e[t1][t2]=t3;
		p[t1][t2]=t2;
		
	}
	for(i=0;i<n;i++)
		dis[i]=e[o][i];
	
	for(i=0;i<n;i++)
		book[i]=0;
	book[o]=1;
	
	for(i=0;i<n;i++)
	{
		min=inf;
		for(j=0;j<n;j++)
		{
			if(book[j]==0&&dis[j]<min)
			{
				min=dis[j];
				u=j;
			};
		};
		book[u]=1;
		for(v=0;v<n;v++)
		{
			if(dis[v]>dis[u]+e[u][v])
			{
				dis[v]=dis[u]+e[u][v];
				p[o][v]=u;
			}
		}
	}
	for(i=0;i<n;i++)
	{
		printf("%d:\n",i);
		if(p[o][i]==inf)
		{	
			printf("no\n");
			continue;
		}
		memset(pa,0,sizeof(pa));
		u=o;v=i;pa[1]=v;t1=2;
		while(1)
		{
			if(p[u][v]!=v)
			{
				pa[t1]=p[u][v];
				v=p[u][v];
				t1++;
			}
			else
			{
				printf("path:%d ",o);
				for(u=t1-1;u>0;u--) printf("%d ",pa[u]);
				printf("\n");
				break;
			};
		};
		printf("cost:%d\n",dis[i]);
		
	};
	return 0;
}