记录编号	333097	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	Zwoi_只会打表抄代码的蒟蒻	是否通过	通过
代码语言	C	运行时间	0.012 s
提交时间	2016-10-29 19:16:02	内存使用	0.45 MiB

#include <stdio.h>
int x[10010],y[10010],z[10010],first[110],next[10010],n,m,k,v,i,book[110],dis[110],que[110],head,tail,map[110],t,f[110],j;
int main()
{
	freopen("djs.in","r",stdin);
	freopen("djs.out","w",stdout);
	scanf("%d%d%d",&n,&m,&v);
	memset(first,-1,sizeof(first));
	memset(book,0,sizeof(book));
	memset(dis,0x3f3f3f3f,sizeof(dis));
	for(i=1;i<=n;i++)
		map[i]=v;
	dis[v]=0;
	head=tail=1;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",x+i,y+i,z+i);
		next[i]=first[x[i]];
		first[x[i]]=i;
	}
	que[tail]=v;
	tail++;
	book[v]=1;
	while(head<tail)
	{
		k=first[que[head]];
		while(k!=-1)
		{
			if(dis[y[k]]>=dis[x[k]]+z[k])
			{
				dis[y[k]]=dis[x[k]]+z[k];
				map[y[k]]=x[k];
				if(book[y[k]]==0)
				{
					que[tail]=y[k];
					tail++;
					book[y[k]]=1;
				}
			}
			k=next[k];
		}
		book[que[head]]=0;
		head++;
	}
	for(i=0;i<n;i++)
	{
		printf("%d:\n",i);
		if(dis[i]==0x3f3f3f3f||dis[i]==0)
			printf("no\n");
		else
		{
			printf("path:%d ",v);
			t=map[i];
			j=0;
			while(t!=v)
			{
				j++;
				f[j]=t;
				t=map[t];
			}
			while(j!=0)
			{
				printf("%d ",f[j]);
				j--;
			}
			printf("%d\n",i);
			printf("cost:%d\n",dis[i]);
		}
	}
	return 0;
}