记录编号	528190	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	增强型图元文件	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2019-02-28 20:53:22	内存使用	3.24 MiB

#include <bits/stdc++.h>
#define inf 9999999
using namespace std;
int n,m,s;
int g[150][150]={0};
bool vis[100]={0};
int d[100]={0};
int p[101]={0};
void print(int l){
	cout<<l<<":"<<endl;
	cout<<"path:";
	int t=l;
	stack<int> st;
	while(t!=s){
		
		st.push(t);
		t=p[t];
	}
	
	cout<<s<<" ";
	while(st.size()){
		cout<<st.top()<<" ";
		st.pop();
	}
    cout<<endl; 	
	cout<<"cost:"<<d[l]<<endl;
}
int main(int argc, char** argv) {
	freopen("djs.in","r",stdin);
	freopen("djs.out","w",stdout);
	cin>>n>>m>>s;
	for(int i=0;i<n;i++){
		d[i]=inf;
		vis[i]=1;
		p[i]=s;
		for(int j=0;j<=n;j++){
			g[i][j]=inf;
		}
	}
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b]=c;
	}
	d[s]=0;
	for(int i=1;i<n;i++){
		int x=-1;
		for(int j=0;j<n;j++){
			if(vis[j]&&x==-1){
				x=j;
				continue;
			}
			if(vis[j]&&d[x]>d[j]){
				x=j;
			}
		}
//		cout<<x<<endl;
		vis[x]=false;
		for(int k=0;k<n;k++){
			if(g[x][k]!=inf&&d[k]>g[x][k]+d[x]){
				d[k]=g[x][k]+d[x];
				p[k]=x;
			}
		}
}

/*	for(int i=0;i<n;i++){
		for(int j=1;j<=n;j++){
			cout<<g[i][j]<<" ";
		}
		cout<<endl;
	}
*/	
	for(int i=0;i<n;i++){
		if(i!=s&&d[i]!=inf){
			print(i);
		}else{
	//		cout<<d[i]<<endl;
			cout<<i<<":"<<endl;
			cout<<"no"<<endl;
		}
	}
	
	return 0;
}