m 条地铁线,分别标号为 1 号线,2 号线,……,m 号线,整个城市一共有。个车站都已知,如果某一站有多条地铁线经过,则可以在这一站换乘到另一条地铁线,并且能多次换乘,现在小雨想从第
小雨所在的城市一共有 m m 条地铁线,分别标号为 1 号线,2 号线,……,m 号线。整个城市一共有 n n 个车站,编号为 1 sim n 1∼n 。其中坐 i 号线需要花费 a_i a i 的价格,每坐一站就需要多花费 b_i b i 的价格。i 号线有 c_i c i 个车站,而且这 c_i c i 个车站都已知,如果某一站有多条地铁线经过,则可以在这一站换乘到另一条地铁线,并且能多次换乘。现在小雨想从第 s s 个车站坐地铁到第 t t 个车站,地铁等待时间忽略不计,求最少花费的价格,若不能到达输出 -1 。(地铁是双向的,所以 s s 可能大于 t t)
(图片来源网络,侵删)