记录编号	83240	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	ranto	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2013-12-01 13:31:16	内存使用	0.27 MiB

#include <fstream>
#include <queue>
#include <set>

using namespace std;

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

struct node{int index;int lenth;node *next;};
struct nodeinfo
{
	int index;
	int lenth;
	int last;
};	
bool operator<(nodeinfo rh, nodeinfo lh)
{
	if(rh.lenth<lh.lenth)
	{
		return true;
	}
	if(rh.lenth==lh.lenth&&rh.last<lh.last)
	{
		return true;
	}
	return false;
}

bool operator>(nodeinfo rh, nodeinfo lh)
{
	if(rh.lenth>lh.lenth)
	{
		return true;
	}
	if(rh.lenth==lh.lenth&&rh.last>lh.last)
	{
		return true;
	}
	return false;
}

nodeinfo makeinfo(int i,int l,int lt){nodeinfo ret;ret.index=i;ret.lenth=l;ret.last=lt;return ret;}

int n,m,v;
node *map;
int *dis;
int *last;

void test_link_list()
{
	for(int i=0;i!=n;++i)
	{
		out<<i<<" : ";
		node *nt(map[i].next);
		do
		{
			out<<'('<<(nt->index)<<','<<(nt->lenth)<<")->";	
			nt=nt->next;
		}while(nt!=NULL);
		out<<"NULL"<<endl;
	}
}

void _init();
void _djs();
void _output();

int main()
{
	_init();
	_djs();
	_output();
	return 0;
}

void _init()
{
	in>>n>>m>>v;
	map=new node [n];
	dis=new int [n];
	last=new int [n];
	for(int i=0;i!=n;++i)
	{
		map[i].index=i;	
		map[i].next=NULL;
		dis[i]=65535;
		last[i]=-1;
	}
	dis[v]=0;
	for(int i=0;i!=m;++i)
	{
		int t1,t2,d;
		in>>t1>>t2>>d;
		node *ntemp=map[t1].next;
		map[t1].next=new node;
		(map[t1].next)->next=ntemp;
		(map[t1].next)->index=t2;
		(map[t1].next)->lenth=d;
	}
	//test_link_list();
	return ;
}

void _djs()
{
	priority_queue<nodeinfo,vector<nodeinfo>,greater<nodeinfo> > nqueue;
	set<int> iset;
	int accesspoint(v);
	iset.insert(accesspoint);
	node *ntemp(map[accesspoint].next);
	while(ntemp!=NULL)
	{
		nqueue.push(makeinfo(ntemp->index,ntemp->lenth,accesspoint));
		ntemp=ntemp->next;
	}
	while(!nqueue.empty())
	{
		nodeinfo nitemp(nqueue.top());
		nqueue.pop();
		if(iset.find(nitemp.index)!=iset.end())
		{
			continue;
		}
		accesspoint=nitemp.index;
		last[accesspoint]=nitemp.last;
		dis[accesspoint]=nitemp.lenth;
		iset.insert(accesspoint);
		ntemp=map[accesspoint].next;
		while(ntemp!=NULL)
		{
			nqueue.push(makeinfo(ntemp->index,ntemp->lenth+dis[accesspoint],accesspoint));
			ntemp=ntemp->next;
		}
	}
	return ;
}

void find(int i)
{
	if(i!=v)
	{
		find(last[i]);
		out<<i<<' ';
		return;
	}
	out<<v<<' ';
}

void _output()
{
	for(int i=0;i!=n;++i)
	{
		out<<i<<':'<<endl;
		if(last[i]==-1)
		{
			out<<"no"<<endl;
			continue;
		}
		out<<"path:";
		find(i);
		out<<endl<<"cost:"<<dis[i]<<endl;
	}
	return ;
}