记录编号	212208	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2015-12-05 18:26:03	内存使用	2.00 MiB

#include<cstdio>
#include<cmath>
using namespace std;
int n,m,v;
int prec[101];
int ans[101];
int dis[101][101];
bool visited[101];
void djs(){
	visited[v] = true;
	int min_v;
	int min_dis;
	for(int i = 2;i<=n;++i){
		min_dis = 1<<20;
		min_v = -1;
		for(int j = 0;j<n;++j){
			if(!visited[j]&&ans[j]<min_dis){
				min_v = j;
				min_dis = ans[j];
			}
		}
		if(min_v==-1)break;
		if(ans[min_v]==dis[v][min_v])prec[min_v] = v;
		for(int j = 0;j<n;++j){
			if(ans[j]>ans[min_v]+dis[min_v][j])
				{
					ans[j] = ans[min_v]+dis[min_v][j];
					prec[j] = min_v;
				}
		}
		visited[min_v] = true;
	}
}
void path(int num){
	if(num!=v)path(prec[num]);
	else{
		 printf("%d",v);
		return;
	}
	printf(" %d",num);
}
void output(int num){
	printf("%d:\n",num);
	if(ans[num]==1<<20){
		printf("no\n");
	}else{
		printf("path:");
		path(num);
		printf("\n");
		printf("cost:%d\n",ans[num]);
	}
}
int main(){
	freopen("djs.in","r",stdin);
	freopen("djs.out","w",stdout);
	scanf("%d %d %d",&n,&m,&v);
	int a,b,c;
	for(int i = 0;i<n;++i)ans[i] = 1<<20;
	ans[v] = 0;
	for(int i = 0;i<n;++i){
		for(int j = 0;j<n;++j)dis[i][j] = 1<<20;
		dis[i][i] = 0;
	}
	for(int i = 0;i<m;++i){
		scanf("%d %d %d",&a,&b,&c);
		dis[a][b] = c;
		if(a==v)ans[b] = c;
	}
	djs();
	ans[v] = 1<<20;
	for(int i = 0;i<n;++i){
		output(i);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}