记录编号	335913	评测结果	WEWEEEEE
题目名称	旅行计划	最终得分	0
用户昵称	Tabing010102	是否通过	未通过
代码语言	C++	运行时间	1.026 s
提交时间	2016-11-02 20:20:33	内存使用	0.31 MiB

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 100+10;
const int INF = 0x3f3f3f3f;
FILE *fin, *fout;
int n, m, s;
struct Edge {
	int from, to, dist;
};
vector<int> G[maxn];
vector<Edge> edges;
void AddEdge(int a, int b, int c) {
	edges.push_back((Edge){a, b, c});
	int m = edges.size();
	G[a].push_back(m-1);
}
struct HeapNode {
	int d, u;
	bool operator < (const HeapNode &rhs) const {
		return d > rhs.d;
	}
};
int d[maxn], p[maxn];
void dijkstra(int s) {
	priority_queue<HeapNode> q;
	for(int i = 0; i < n; i++) d[i] = INF;
	d[s] = 0;
	q.push((HeapNode){0, s});
	while(!q.empty()) {
		HeapNode x = q.top(); q.pop();
		int u = x.u;
		if(x.d != d[u]) continue;
		for(int i = 0; i < G[u].size(); i++) {
			Edge &e = edges[G[u][i]];
			if(d[e.to] > d[u]+e.dist) {
				d[e.to] = d[u]+e.dist;
				p[e.to] = G[u][i];
				q.push((HeapNode){d[e.to], e.to});
			}
		}
	}
}
void print_path(int now) {
	if(edges[now].from == s) { fprintf(fout, "%d ", s); return; }
	print_path(edges[p[now]].from);
	fprintf(fout, "%d ", now);
}
int main() {
	fin = fopen("djs.in", "r");
	fout = fopen("djs.out", "w");
//	fout = stdout;
	fscanf(fin, "%d%d%d", &n, &m, &s);
	for(int i = 0; i < n; i++) G[i].clear();
	edges.clear();
	for(int i = 1; i <= m; i++) {
		int a, b, c;
		fscanf(fin, "%d%d%d", &a, &b, &c);
		AddEdge(a, b, c);
	}
	dijkstra(s);
	for(int i = 0; i < n; i++) {
		fprintf(fout, "%d:\n", i);
		if(i==s || d[i]>=INF) fprintf(fout, "no");
		else {
			fprintf(fout, "path:");
			print_path(i);
			fprintf(fout, "\ncost:%d", d[i]);
		}
		fprintf(fout, "\n");
	}
	return 0;
}