记录编号	471449	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	snake	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2017-11-06 14:43:50	内存使用	0.32 MiB

//#include<iostream>
#include<cstring>
#include<climits>
#include<ctime>
#include<fstream>
#include<queue>
#include<stack>
using namespace std;
ifstream cin("djs.in");ofstream cout("djs.out");

struct edge
{
	int dis;
	int to;
};

const int MAX=110;
vector<edge> map[MAX];
queue<int> q;
int shortest[MAX];
int n,m,v;
bool inqueue[MAX];
int last[MAX];

void spfa(int x)
{
	for(int i=0;i<n;i++) shortest[i]=INT_MAX;
	shortest[x]=0;
	q.push(x);
	inqueue[x]=1;
	
	while(!q.empty())
	{
		int t=q.front();
		for(unsigned int i=0;i<map[t].size();i++)
		{
			if(shortest[map[t][i].to]>shortest[t]+map[t][i].dis)
			{
				shortest[map[t][i].to]=shortest[t]+map[t][i].dis;
				if(!inqueue[map[t][i].to]){q.push(map[t][i].to);inqueue[map[t][i].to]=1;}
				last[map[t][i].to]=t;
			}
		}
		q.pop();
		inqueue[t]=0;
	}
	
	return;
}

void path(int x)
{
	int l=x;
	stack<int> s;
	while(l!=v)
	{
		s.push(l);
		l=last[l];
	}
	s.push(v);
	
	while(!s.empty())
	{
		cout<<s.top()<<" ";
		s.pop();
	}
	
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m>>v;
	for(int i=1;i<=m;i++)
	{
		int x,y,dis;
		cin>>x>>y>>dis;	//x to y
		edge t;
		t.dis=dis;
		t.to=y;
		map[x].push_back(t);
	}
	
	spfa(v);
	
	for(int i=0;i<n;i++)
	{
		cout<<i<<":\n";
		if(shortest[i]==0 || shortest[i]==INT_MAX) cout<<"no\n";
		else
		{
			cout<<"path:";
			path(i);
			cout<<"\ncost:"<<shortest[i]<<endl;
		}
	}
	
	return 0;
}

/*
5 7
1 2 50
1 4 10
2 3 2
3 1 15
3 5 30
4 2 16
4 5 20
*/