当前位置:首页 > 图论 > 最短路径 > 正文
SSOJ2552地铁路线
598+

题目大意:n个点m条边,从x点到y点的最短路程是多少?这条路径依次经过哪些点?

题目描述

公元8888年,大部分地球居民都迁移至S星球。在S星球,有n个城市,m段高速地铁。地铁是按路程来收费的,举个例子,城市1到城市n的路程是99公里,那么收取99个S币。如果城市1到城市n有多条路径可以选择,按最短那条路来收费。
现在,有一个好人要坐地铁,他要从城市x坐到城市y,请问他需要花费多少个S币?
为什么说他是好人呢?因为他从来不做“损人”的事情。比如说,他做地铁,从x到y,可以有很多条线路,有些线路长,有些线路短,如果选了线路长的,那么地铁不就“亏”了吗?因此,他会选择最短那条线路。请输出这个好人坐地铁的行走路线。

输入

第一行:4个整数n、m、x、y
接下来m行,每行3个整数a、b、c,表示城市a到城市b的路程是c公里

输出

第一行:输出费用
第二行:输出路线
(如果不能到达,仅输出一行,即一个0)

样例输入

5 5 1 3
1 2 5
2 3 8
1 4 2
4 5 2
5 3 2

样例输出

6
1 4 5 3

提示

数据范围
5 <= n <= 10000
10 <= m <= 100000
1 <= a、b <= n
1 <= c <= 100
60%的数据:n <= 5000
80%的数据:n <= 8000

解题思路

在上一题《地铁费用》的基础上,记录最短路径中各个点的前驱,最后递归输出这条路线即可。由于只需要求x到y的最短路径,因此,用迪杰斯特拉算法,当y的最短路径确定后,就可以不再继续更新找其他点的最短路了,这样就可以在时间上充裕很多。(最短路径求法有问题,请看上一篇文章)

程序实现

更多
SSOJ2552地铁路线:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter