记录编号	228412	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2016-02-19 10:49:32	内存使用	0.27 MiB

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <ctype.h>
#include <queue>
using namespace std;

int fast_read_int()
{
	int ret;
	char ch;
	while(ch = getchar())
	{
		if(ch >= '0' && ch <= '9')
		{
			ret = ch ^ 0x30;
			break;
		}
	}
	while(isdigit(ch = getchar()))ret = (ret << 3)+(ret << 1)+(ch^0x30);
	return ret;
}
int n, m, s;

struct edge
{
	int v,c;
};
vector<edge> adj[101];
int path[101];
int in_q[101];
int cost[101];
void spfa()
{
	int i;
	int u, v, c;
	queue<int> q;
	for(i = 0; i < n; i++)
	{
		cost[i] = 0x23333333;
	}
	cost[s] = 0;
	in_q[s] = 1;
	q.push(s);
	while(q.size())
	{
		u = q.front();
		q.pop();
		for(i = 0; i < adj[u].size(); i++)
		{
			v = adj[u][i].v;
			c = adj[u][i].c;
			if(cost[v] > cost[u] + c)
			{
				cost[v] = cost[u] + c;
				path[v] = u;
				if(!in_q[v])
				{
					q.push(v);
					in_q[v] = 1;
				}
			}
		}
		in_q[u] = 0;
	}
}

int last[101];
void print_res(int id)
{
	if(cost[id] == 0x23333333 || cost[id] == 0)
	{
		puts("no");
		return;
	}
	int j, c = 0;
	j = id;
	while(true)
	{
		last[c] = j;
		c++;
		if(j == s)break;
		j = path[j];
	}
	printf("path:");
	for(j = c - 1; j >= 0; j--)
	{
		printf("%d ", last[j]);
	}
	printf("\n");
	printf("cost:%d\n", cost[id]);
}

int main()
{
	freopen("djs.in", "r", stdin);
	freopen("djs.out", "w", stdout);
	int i, u, v, c;
	n = fast_read_int();
	m = fast_read_int();
	s = fast_read_int();
	for(i = 0; i < m; i++)
	{
		u = fast_read_int();
		v = fast_read_int();
		c = fast_read_int();
		adj[u].push_back(edge{v, c});
	}
	spfa();
	for(i = 0; i < n; i++)
	{
		printf("%d:\n", i);
		print_res(i);
	}
	return 0;
}