公交最小票价 - Hangzhou High School OJ

_{[命题人 : 2211247]}

时间限制 : 1.000 sec 内存限制 : 128 MB

在一个城市里有几条公交线路，有人想尽可能省钱地从所在的0站前往目标站点，请编写程序帮助他实现这一功能。

第一行：一个整数k，表示有k条线路
第二行：一个整数m，表示目标站点
接下来k行：不同公交线路及其票价，线路在前，各站间用-分隔；票价在后，线路和票价之间用空格分隔
注意：
1、确保站点编号有且只有0-m
2、票价为浮点数（float）

最少票价（保留1位小数）

6
18
0-2-3-11-16 2.5
0-1-4-12-15 3.0
1-5-7-10-18 2.5
1-5-9-12-17 1.5
2-6-9-13-16-18 3.0
3-8-14-18 4.0

5.5

该城市的公交车均为单向，不能坐回程。

无

动态规划广度优先搜索

提交