记录编号	24802	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2011-04-27 21:49:06	内存使用	0.34 MiB

#include <fstream>
using namespace std;

ifstream input("djs.in");
ofstream output("djs.out");

const int MAX=1000000000;
int n,m,v,nn,vv,t1,t2,map[101][101][2],way[101],path[101],cost[101];
bool used[101];

void printit(int x)
{
	if (x==v)
		output<<x;
	else
	{
		printit(path[x]);
		output<<' '<<x;
	}
}

int main(void)
{
	int i;
	input>>n>>m>>v;
	nn=n;
	vv=v;
	for (i=1;i<=m;i++)
	{
		input>>t1;
		way[t1]++;
		input>>map[t1][way[t1]][0]>>map[t1][way[t1]][1];
	}
	for (i=0;i<n;i++)
	{
		cost[i]=MAX;
		path[i]=vv;
	}
	while (nn>0)
	{
		used[vv]=true;
		if (vv==v)
			for (i=1;i<=way[vv];i++)
				cost[map[vv][i][0]]=map[vv][i][1];
		else
			for (i=1;i<=way[vv];i++)
				if (map[vv][i][1]+cost[vv]<cost[map[vv][i][0]])
				{
					cost[map[vv][i][0]]=map[vv][i][1]+cost[vv];
					path[map[vv][i][0]]=vv;
				}
		t1=MAX+1;
		for (i=0;i<n;i++)
			if (used[i]==false&&cost[i]<t1)
			{
				t1=cost[i];
				vv=i;
			}
		nn--;
	}
	for (i=0;i<n;i++)
	{
		output<<i<<":\n";
		if (cost[i]==MAX||i==v)
			output<<"no\n";
		else
		{
			output<<"path:";
			printit(i);
			output<<"\ncost:"<<cost[i]<<endl;
		}
	}
	input.close();
	output.close();
	return(0);
}