問題文
当我离开数据中心时,外面的太阳已经升得很高了。
反正我很困。 Niconico的同步维护从凌晨2点左右开始,按计划于上午10点左右结束。虽然我没有加班,但我不太擅长改变自己的生活节奏,所以在维护开始前我并没有睡多少觉。我想尽快回家,钻进被窝里……但在此之前,我担心自己是否能安全回家,而不会在火车上睡过头。
N 站和 M 有一个由火车线路组成的火车网络。每条线路均可双向使用,并且一条线路绝不会在同一车站多次停靠。
我使用这个火车网络 src 从车站 我想转到 dst 。但每当您乘坐火车并在该线路的车站之间移动时,您都可能会睡着。如果你睡着了,你会经过原定下车的车站,然后继续乘车到你行驶方向的最后一站。在终点站醒来后,您会感到神清气爽,从此您不会错过火车,可以通过任何您喜欢的路线前往目的地车站。
不幸的是,我最终在工作中喝了能量饮料,但我的身体仍然没有摆脱咖啡因。换句话说,你永远无法预测自己何时会在旅途中睡着。
我想好好选择我的旅行路线,这样如果我在最糟糕的时间睡着了,我最终的旅行时间就会最小化。在这种情况下,旅行需要多少时间?
入力
输入采用以下格式给出。
N M src dst
L_{0}
s_{0,0} s_{0,1} ... s_{0,L_{0}-1}
w_{0,0} w_{0,1} ... w_{0,L_{0}-2}
L_{1}
s_{1,0} s_{1,1} ... s_{1,L_{1}-1}
w_{1,0} w_{1,1} ... w_{1,L_{1}-2}
:
在第一行 给出 N, M, src, dst (0 \leq src, dst < N) ,并在下一行中给出行信息。
每条路线的信息分三行给出。第一行显示线路上的车站数量。 给出了 L_{i} 。第二行按顺序给出了线路停靠的车站。第三行显示车站之间的旅行时间。 给定 L_{i} - 1 整数, 第 j 号是该路线的号码。 j 第站和 表示第 j+1 个车站之间所需的时间(无论前往哪个车站所需的时间都是相同的)。路线的 从第 j 站出发 j+1 如果您在前往第 站的途中睡过头。 您将前往线路的 L_{i} - 1 站。 您将前往 j+1 站出发 j 如果您在前往第 站的途中睡过头。 您将前往线路的 0 站。请注意,可能有多条线路直接连接同一车站,在这种情况下,各线路的行程时间可能会有所不同。
输入满足以下约束。
- 2 \leq N \leq 25,252
- 2 \leq L_{i} (0 \leq i < M)
- L_{0} + L_{1} + ... + L_{M-1} \leq 252,525
- 1 \leq w_{i,j} \leq 2,525
- src \neq dst
- 没有线路在同一车站停靠多次。也就是说,j \neq k ならば s_{i,j} \neq s_{i,k}
- src 和 dst 之间有一条或多条路线
配点
设置了部分点,50 点的数据集还满足以下约束。
- N \leq 252
- L_{0} + L_{1} + ... + L_{M-1} \leq 525
- w_{i,j} \leq 25
出力
在一行中输出问题中询问的行程时间。不要忘记输出末尾的换行符。 最佳路线是在前往
入力例1
5 2 0 3 3 0 1 2 1 2 3 1 3 4 1 1
出力例1
6
駅 0 它们的编号最大为 1 的途中避免睡过头。 0 - 1 - 2 - 1 - 3 成本是 6 。
入力例2
5 2 0 3 3 0 1 2 1 1 3 1 3 4 1 3
出力例2
8
列车网络与输入示例 1 相同,但唯一的区别是车站之间的行程时间。这使得该站 0 - 1 而不是在之间睡过头 1 - 3 中间睡觉的时间会更长。
请注意,您无法控制在移动时何时睡着。车站 0 - 1 - 2 无论你如何在两者之间移动,你都想不出一条会在这里睡过头的路线。车站 要到达 3 ,您必须前往车站。 1 - 3 这是因为你必须从一个地方搬到另一个地方,如果你在这里睡过头,你会得到更糟糕的结果。
入力例3
4 2 0 1 3 0 1 2 1 3 3 0 3 1 1 1
出力例3
2
如果你使用第一条路线,如果你睡过头了,你会被带到很远的地方。二号线的目的地是终点站,所以无论你在哪里睡过头,都会节省你的时间。 2 保证您将到达目的地。