记录编号	486229	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	HtBest	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2018-02-05 23:32:02	内存使用	0.24 MiB

#define _CRT_SECURE_NO_DEPRECATE
/************************
*创建时间：2018 02 05
*文件类型：源代码文件
*题目来源：COGS
*采用算法：Floyd
*作者：HtBest
************************/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int n, m, v, a[100][100], road[100][100];
/* Variable explain:

*/
void h1()
{
	for (int i = 0; i<n; ++i)
		for (int j = 0; j<n; ++j)
			a[i][j] = 1e9;
	memset(road, -1, sizeof(road));
	return;
}
void read()
{
	freopen("djs.in","r",stdin);
	freopen("djs.out","w",stdout);
	scanf("%d%d%d", &n, &m, &v);
	h1();
	register int ls1, ls2;
	for (int i = 0; i<m; ++i)
	{
		scanf("%d%d", &ls1, &ls2);
		scanf("%d", &a[ls1][ls2]);
	}
	return;
}
void floyd()
{
	for (int k = 0; k<n; ++k)
		for (int i = 0; i<n; ++i)
			for (int j = 0; j<n; ++j)
			{
				if (a[i][k]<1e9&&a[k][j]<1e9&&a[i][j]>a[i][k] + a[k][j])
				{
					a[i][j] = a[i][k] + a[k][j];
					road[i][j] = k;
				}
			}
	return;
}
void prroad(int v, int i)
{
	if (road[v][i] == -1)	return;
	prroad(v, road[v][i]);
	printf(" %d", road[v][i]);
	prroad(road[v][i], i);
	return;
}
void print()
{
	for (int i = 0; i<n; ++i)
	{
		printf("%d:\n", i);
		if (i == v || a[v][i] >= 1e9)	printf("no\n");
		else
		{
			printf("path:%d", v);
			prroad(v,i);
			printf(" %d\n", i);
			printf("cost:%d\n", a[v][i]);
		}
	}
	return;
}
int main()
{
	read();
	floyd();
	print();
	return 0;
}