解题思路

给定若干条电车线路，每条线路有固定票价 price，并给出它依次经过的一组站点。上车一次只收该线路的固定票价，在线路内任意移动不再收费；在换乘点（出现在多条线路中的同一站点）换乘到另一条线路时，需要再付那条线路的票价。求从起点站 X 到终点站 Y 的最小总票价；若不可达或最小票价大于身上钱数 Z，输出 -1。

建模与算法

• 将“站点内免费移动、换乘才付费”转化为线路图： 把每一条电车线路看作图中的一个节点；若两条线路有共同站点，则在它们之间连一条无权边。
• 费用在“进入一条线路时支付”。因此可在节点带权图上跑最短路：

题目内容

为了方便城市居民有序流动，城市 $A$ 开通了一系列有轨电车路线，每列电车会沿固定的路线循环行驶，电车票价实行一票制，不论乘坐多少站，均按固定价格收费，循环坐车时不重复收费。请计算你在城市里面，从出发点到目的地，乘坐电车的最低费用。

输入描述

第 $1$ 行：$M$ $X$ $Y$ $Z$ ，其中：$M$ 代表电车线路总数量，$X$ 代表起点编号，$Y$ 代表终点编号，$Z$ 代表身上的金钱数。$1<=M<=50;0<=X,Y<=500;X丨=Y:1<=Z<=500$ 。输入以空格分隔。下面跟着 $M$ 行相同格式的数据。

第 $2$ 行：$price$ $n$ $station_1$ $station_2$ $station_3$ - $sation_n$ ，其中：$price$ 代表本条电车线路的票价，$n$ 代表本条电车路线经过的站点数量、后面跟着 $n$ 个数字，$station_1,station_2,station_3,...,station_n$ 代表本条电本线路经过的站点的站点编号，站点编号可能比站点总的数星大，$station_n$ 可能大于 $n$ 。$1<=n<=10,0<=station_n<=500;1<=price<=10$;

第 $M+1$ 行：$price$ $n$ $station_1$ $staton_2$ $sation_3$ ... $station_n$ 。

输出描述

需要花费的金钱数。如果无法达到或身上的金钱数不够达到，返回 $-1$ 。

样例1

输入

5 15 12 4
2 2 7 12
3 3 4 5 15
4 1 6
3 2 15 7
1 3 12 13 7

输出

4

说明

共 $5$ 条电车路线，要求从 $15$ 到 $12$，可选路线包括：

$a$：乘坐线路 $4(15->7)$ ，在 $7$ 站点换乘线路 $1(7->12)$

$b$ ：乘坐线路 $4(15->7)$ ，在 $7$ 站点换乘线路 $5(7->3->12->13)$

第二种乘坐方式花费更小，只需要 $4$

样例2

输入

2 1 6 5
2 3 1 2 7
3 3 3 6 7

输出

5

说明

从第一行输入可知，电车线路总数为 $2$ ，出发点编号为 $1$ ，终点编号为 $6$ ，身上的金钱数为 $5$ 。后面接着有 $2$ 行不定长数据。

从第二行输入可知，第一条电车路线的票价为 $2$ ，经过 $3$ 个站点，站点路线为 $[1,2,7]$ 。

从第三行输入可知，第二条电车路线的票价为 $3$ ，经过 $3$ 个站点，点路线为 $[3,6,7]$ 。

分析可得最优的乘坐策略是在 $1$ 站点先乘坐第一辆电车到达车站 $7$ ，然后换乘第二辆电车到车站 $6$ 。共花费金钱 $5$ ，没有超过身上的金钱数 $5$ ，故应返回结果 $5$ 。