记录编号	191507	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2015-10-07 21:26:26	内存使用	0.32 MiB

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
#include <climits>

using namespace std;

ifstream fin("djs.in");
ofstream fout("djs.out");
#define cin fin
#define cout fout
const int MAXN(101), INF(INT_MAX / 3);
int n, m, s, f[MAXN], p[MAXN], u, v;
vector<int> g[MAXN], c[MAXN];
inline void dijkstra(int);
void find_path(int);
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;

main()
{
	ios::sync_with_stdio(false);
	cin >> n >> m >> s;
	for (int i = 1; i <= m; ++i){
		int x, y, z;
		cin >> x >> y >> z;
		g[x].push_back(y);
		c[x].push_back(z);
	}
	fin.close();
	
	dijkstra(s);
	
	fout.close();
//	for (; ; );
}

inline void dijkstra(int s){
	bool l[MAXN] = {false};
	fill(l, l + n + 1, false);
	l[s] = true;
	fill(f, f + n + 1, INF);
	f[s] = 0;
	q.push(make_pair(f[s], s));
	while (! q.empty()){
		u = q.top().second;
		q.pop();
		for (int i = 0; i < g[u].size(); ++i){
			v = g[u][i];
			if (f[v] > f[u] + c[u][i]){
				f[v] = f[u] + c[u][i];
				p[v] = u;
				if (! l[v]){
					l[v] = true;
					q.push(make_pair(f[v], v));
				}
			}
		}
	}
	for (v = 0; v < n; ++v){
		cout << v << ":\n";
		if (f[v] == INF || v == s)
			cout << "no\n";
		else{
			cout << "path:";
			find_path(v);
			cout << "cost:" << f[v] << endl;
		}
	}
}

void find_path(int node)
{
	if (node == s)
		cout << node << ' ';
	else{
		find_path(p[node]);
		cout << node;
		if (node != v)
			cout << ' ';
		else
			cout << endl;
	}
}