首页 > 试题广场 >

小雨坐地铁

[编程题]小雨坐地铁
  • 热度指数：3 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 512M，其他语言1024M
  • 算法知识视频讲解
小雨所在的城市一共有 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。整个城市一共有 个车站，编号为 。其中坐 i 号线需要花费 的价格，每坐一站就需要多花费 的价格。i 号线有 个车站，而且这 个车站都已知，如果某一站有多条地铁线经过，则可以在这一站换乘到另一条地铁线，并且能多次换乘。现在小雨想从第 个车站坐地铁到第 个车站，地铁等待时间忽略不计，求最少花费的价格，若不能到达输出 -1 。（地铁是双向的，所以 可能大于 ）

输入描述:
第一行输入四个正整数 ，分别表示车站个数，地铁线数，起点站和终点站。
第二行到第  行，每行前三个数为 ，分别表示坐 i 号线的价格，i 号线每坐一站多花的价格，i 号线车站个数。接下来 c_i 个数，表示 i 号线的每一个车站的编号，单调递增。


输出描述:
共一行，一个数表示最小花费，若不能到达输出 -1 。
示例1

输入

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

输出

7

说明

坐 1 号线：花费 2；

1 \rightarrow 3：花费 2；

换乘 2 号线：花费 2；

3 \rightarrow 4：花费 1；

所以最小总花费为 7 。

备注:


算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 12浏览

热门推荐

通过挑战的用户

查看代码

相关试题

小雨坐地铁

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号