记录编号	464260	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	Regnig Etalsnart	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-10-25 15:33:11	内存使用	0.00 MiB

#include<cstdio>
#include<cstring>
#include<queue>
#define syy myson
using namespace std;
const int INF=1000000000;
int n,m,V,cnt,head[10001],inque[101]={0},dist[101],path[101],i;
struct Edge
{
	int to,next,w;
}e[10001];
void add(int u,int v,int w)
{
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt++;
}
void spfa()
{
	queue<int>q;
	for(i=0;i<n;i++)dist[i]=INF;
	q.push(V);
	inque[V]=1;
	dist[V]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(i=head[u];~i;i=e[i].next)
		{
			int v=e[i].to,w=e[i].w;
			if(dist[v]>=dist[u]+w)
			{
				dist[v]=dist[u]+w;
				path[v]=u;
				if(!inque[v])
				{
					q.push(v);
					inque[v]=1;
				}
			}
		}
		inque[u]=0;
	}
}
int Main()
{
	freopen("djs.in","r",stdin);freopen("djs.out","w",stdout);
	memset(head,-1,sizeof(head));
	scanf("%d%d%d",&n,&m,&V);
	while(m--)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	spfa();
	for(i=0;i<n;i++)
	{
		printf("%d:\n",i);
		if((dist[i]>=INF)||(i==V)){printf("no\n");continue;}
		int p=i,P[101]={0},num=0;
		while(p!=V)
		{
			P[++num]=p;
			p=path[p];
		}
		printf("path:%d ",V);
		for(int j=num;j>=1;j--)printf("%d ",P[j]);
		printf("\ncost:%d\n",dist[i]);
	}
	return 0;
}
int main(){;}
int syy=Main();