记录编号	191211	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	Dissolute丶Tokgo	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2015-10-06 19:23:22	内存使用	0.32 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define INF 99999999
#define N 111
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define rep2(i,l,r) for(int i=l;i<r;++i)
#define drep(i,r,l) for(int i=r;i>=l;--i)

struct Edge{
	int from,to,dist;
	Edge(int u,int v,int d):from(u),to(v),dist(d){}
};

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

vector<Edge>edges;
vector<int>G[N];
stack<int>S;
priority_queue<Heapnode>Q;
int n,m,st,cnt=0,d[N],p[N];
bool done[N];

inline int qread(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret;
}

inline void out(){
	rep2(i,0,n){
		printf("%d:\n",i);
		if(d[i]==INF||d[i]==0)
		    printf("no\n");
		else{
			int top=0,j=i;
			while(j!=st){
				S.push(j);
				j=edges[p[j]].from;
			}
			printf("path:%d ",st);
			while(!S.empty()){
				printf("%d ",S.top());
				S.pop();
			}
			printf("\ncost:%d\n",d[i]);
		}
	}
}

inline void dij(){
	rep2(i,0,n) d[i]=INF;
	d[st]=0;
	memset(done,0,sizeof(done));
	Q.push(Heapnode(st,d[st]));
	while(!Q.empty()){
		Heapnode x=Q.top();
		Q.pop();
		int u=x.u;
		if(done[u]) continue;
		done[u]=true;
		rep2(i,0,G[u].size()){
			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(e.to,d[e.to]));
			}
		}
	}
}

inline void in(){
	freopen("djs.in","r",stdin);
	freopen("djs.out","w",stdout);
	n=qread(),m=qread(),st=qread();
	rep(i,1,m){
		int u=qread(),v=qread(),d=qread();
		edges.push_back(Edge(u,v,d));
		G[u].push_back(cnt++);
	}
}

int main(){
	in();
	dij();
	out();
}