1401-一场说走就走的旅行


    内存限制:64MB 时间限制:1000ms 特判: No

    通过数:1 提交数:39 难度:3


题目描述:

有一天,孩子回来对我说:妈妈,听说马尔代夫很不错,放假了我想去玩。马尔代夫?我也想去!没有人不向往一场说走就走的旅行!其实我想去的地方很多,呼伦贝尔大草原、玉龙雪山、布达拉宫、艾菲尔铁塔……小孩子还说着他感兴趣的地方。于是我们拿出地图,标出想去的地点,然后计算最短路线,估算大约所需的时间,有了这张秘制地图,一场说走就走的旅行不是梦!

给定有向带权图G =V,其中每条边的权是非负实数。此外,给定V中的一个顶点,称为源点。现在要计算从源到所有其他各顶点的最短路径长度,这里路径长度指路上各边的权之和。


输入描述:

第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是两个整数n,c(1<n,c<1000)表示该测试数据有n个城市c条边。
随后的c行,每行有3个正整数u,v,w(0<u,v<=n, 0<w<10000),分别表示边的两个顶点编号u,v及两顶点之间的距离。
最后一行,源点的编号s(0<s<=n)。

输出描述:

对于每一组输入,输出n个整数,代表源点到其它顶点的最短距离。如果源点不能到达其他顶点输出“impossible”。
每组的输出占一行。

样例输入:

2
5 11
1 5 12
5 1 8
1 2 16
2 1 29
5 2 32
2 4 13
4 2 27
1 3 15
3 1 21
3 4 7
4 3 19
5
3 5
1 2 6
1 3 13
2 1 10
2 3 4
3 1 5
1

样例输出:

8 24 23 30 0
0 6 10

提示:


上传者:rainflychxy

书中题目链接,请点击上面链接访问!

公告

    欢迎使用NYOJ2.0!