记录编号	154827	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2015-03-25 11:12:31	内存使用	0.44 MiB

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <stack>
#include <map>
using namespace std;
const int MAXN=100+5;
const int MAXW=10000000;
int G[MAXN][MAXN];
int P[MAXN][MAXN];
int N[MAXN][MAXN];
 
void walk(int s,int e)
{
if(s==e) return;
cout<<s<<" ";
if(G[s][N[s][e]]==MAXW)
	walk(N[s][N[s][e]],N[s][e]);
walk(N[s][e],e);
}
 
int main()
{
freopen("djs.in","r",stdin);
freopen("djs.out","w",stdout);
int n,m,v,x,y;
cin>>n>>m>>v;
for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
		G[i][j]=MAXW;
for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
		N[i][j]=j;
 
for(int i=0;i<m;i++)
	{
	cin>>x>>y;
	cin>>G[x][y];
	}
 
for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
		P[i][j]=G[i][j];
 
for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
		for(int k=0;k<n;k++)
			if(P[i][k]+P[k][j]<P[i][j])
				{
				P[i][j]=P[i][k]+P[k][j];
				N[i][j]=k;
				}
 
for(int i=0;i<n;i++)
	{
	cout<<i<<":"<<endl;
	if(P[v][i]==MAXW||i==v) cout<<"no"<<endl;
	else
		{
		cout<<"path:";
		walk(v,i);
		cout<<i<<endl<<"cost:"<<P[v][i]<<endl;
		}
	}
 
return 0;
}