记录编号	204090	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	God-Nan	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2015-11-03 21:27:57	内存使用	0.44 MiB

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
void clear(int x);
void addpoint(int f,int t,int p);
void cool(int u);
int father[110],head[110],next[11000],to[11000],power[11000];
int dis[110],start;
bool flag[110];
struct dota
{
	int from,to,power;
	bool operator <(const dota&a)const
	{
		if(power!=a.power)
	  return power>a.power;
	  else
	   return to>a.to;
    }
};
int main()
{
	freopen("djs.in","r",stdin);
	freopen("djs.out","w",stdout);
	int n,m,s,i,p,k,f,t;
	scanf("%d%d%d",&n,&m,&s);
	
	for(i=0;i<=109;i++)
	{
		dis[i]=999999999;
		head[i]=-1;
		father[i]=i;
	}
	
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&f,&t,&p);
		addpoint(f,t,p);
	}
	cool(s);
	for(i=0;i<=n-1;i++)
	{
	  printf("%d:\n",i);
	  if(dis[i]==0||dis[i]==999999999)
	  {printf("no\n");continue;}
	  else
	  {
	  	printf("path:");
	  	 clear(i);
	  	printf("%d\n",i);
	  	printf("cost:%d\n",dis[i]);
	  }
	}
	return 0;
}
void addpoint(int f,int t,int p)
{
	next[++start]=head[f];
	to[start]=t;
	head[f]=start;
	power[start]=p;
	return ;
}
void cool(int u)
{
     	priority_queue<dota> dui;
     	dui.push((dota){0,u,0});
     	dis[u]=0;
     	while(!dui.empty())
     	{
     		dota we=dui.top();dui.pop();
     		if(flag[we.to])
     		continue;
     		else
     		 flag[we.to]=1;
     		
     		int point=head[we.to];
     		while(point!=-1)
     		{
     		    if(dis[to[point]]>dis[we.to]+power[point])
     		    {
     		      dis[to[point]]=dis[we.to]+power[point];
				  dui.push((dota){we.to,to[point],dis[to[point]]});
				  father[to[point]]=we.to;
     		    }
     		    point=next[point];
     		}
     	}
}
void clear(int x)
{
	if(x==father[x])
	return ;
	else
	 clear(father[x]);
	 
	 printf("%d ",father[x]);
	 return ;
}