记录编号	337339	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	Hoohan(%Dalao)	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2016-11-04 10:49:06	内存使用	0.24 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstdlib>

using namespace std;

const int maxn=110,maxm=10010,maxdist=0x3f3f3f3f;

struct Edge{
	int from,to,dist;
};

struct heapnode{
	int d,u;
	bool operator < (const heapnode & x) const{
		return d > x.d;
	}
};

int n,m,start;
vector <Edge> edges;
vector <int> G[maxn];
bool done[maxn];
int d[maxn];
int p[maxn];

void addedge(int a,int b,int c)//from to dist
{
	edges.push_back( (Edge) {a,b,c} );
	int ls=edges.size();		//ԭΪM 
	G[a].push_back(ls-1);
}

void dij(int s)
{
	priority_queue <heapnode> q;
	for(int i=0;i<n;i++) d[i]=maxdist;
	d[s]=0;
	memset(done,0,sizeof(done));
	q.push((heapnode) {0,s});
	while(!q.empty())
	{
		heapnode x=q.top();q.pop();
		int u=x.u;
		if(done[u]) continue;
		done[u]=true;
		for(int i=0; i < G[u].size() ;i++)
		{
			Edge &e = edges[G[u][i]];
			if(d[e.to] > d[u]+e.dist)
			{
				d[e.to]=d[u]+e.dist;
				p[e.to]=G[u][i];
				q.push((heapnode) {d[e.to],e.to});
			}
		}
	}
}

void print_path(int now)
{
	if(edges[p[now]].from==start) {
		cout<<start<<' ';
		return;
	}
	print_path(edges[p[now]].from);
	cout<<edges[p[now]].from<<' ';
}

int main()
{
	freopen("djs.in","r",stdin);
	freopen("djs.out","w",stdout);
	cin>>n>>m>>start;
	for(int i=0;i<n;i++) G[i].clear();
	edges.clear();
	int a,b,c;
	for(int i=0;i<m;i++)
	{
		cin>>a>>b>>c;
		addedge(a,b,c);
	}
	dij(start);
	
//	for(int i=0;i<n;i++) cout<<d[i]<<' ';
//	cout<<endl;
//	for(int i=0;i<n;i++) cout<<p[i]<<' ';
//	cout<<endl;
	
	for(int i=0;i<n;i++)
	{
		cout<<i<<':'<<endl;
		if(d[i]==maxdist || d[i]==0)
		{
			cout<<"no"<<endl;
		}
		else{
			cout<<"path:";
			print_path(i);
			cout<<i<<endl<<"cost:"<<d[i]<<endl;
		}
	}
	return 0;
}