时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld
题目描述
小雨所在的城市一共有

条地铁线,分别标号为 1 号线,2 号线,……,m 号线。整个城市一共有

个车站,编号为

。其中坐 i 号线需要花费

的价格,每坐一站就需要多花费

的价格。i 号线有

个车站,而且这

个车站都已知,如果某一站有多条地铁线经过,则可以在这一站换乘到另一条地铁线,并且能多次换乘。现在小雨想从第

个车站坐地铁到第

个车站,地铁等待时间忽略不计,求最少花费的价格,若不能到达输出
-1 。(地铁是双向的,所以

可能大于

)
输入描述:
第一行输入四个正整数
,分别表示车站个数,地铁线数,起点站和终点站。
第二行到第
行,每行前三个数为
,分别表示坐 i 号线的价格,i 号线每坐一站多花的价格,i 号线车站个数。接下来
个数,表示 i 号线的每一个车站的编号,单调递增。
输出描述:
共一行,一个数表示最小花费,若不能到达输出 -1 。
示例1
输入
复制
5 2 1 4
2 2 3 1 3 5
2 1 4 2 3 4 5
说明
坐 1 号线:花费 2;
:花费 2;
换乘 2 号线:花费 2;
:花费 1;
所以最小总花费为 7 。
备注:

