問題文
在每个车站, 分配的唯一站号最多为0减去N-1。
每条路线都不同2它连接两个车站,可用于任一方向行驶。
QU铁路也使用票价表,根据距离分阶段改变票价。
从 A 站到 B 站的车票价格是根据 A 站到 B 站的最短距离从票价表中确定的。
例如,请考虑以下路线图和票价表。
| 距離 | 運賃 |
|---|---|
| 1 公里- 6 km | 180 円 |
| 7 公里- 15 km | 230 円 |
| 16 公里- 25 km | 400 円 |
| 26 公里- 40 km | 530 円 |
| 41 公里- 60 km | 740 円 |
| 61 公里或以上 | 820 円 |
在此示例中,该站0从车站6的票价。 到
駅0从车站6的总距离是41公里,所以 从票价表来看,车站 前往0从车站6的机票是740变成日元。
QU 铁路还允许您使用不同路段的多张车票从一个车站前往另一个车站。
这称为票证拆分。
例如,以下2如果您有一张票,您可以 您可以向上移动到0从车站6。
- 駅0从车站1的机票: 6公里,180円
- 駅1从车站6的机票: 35公里,530円
这样一来,在QU铁路上,存在通过分票来降低票价的情况。
另外,如下:3门票可用于 考虑移动到0从车站6的情况。
- 駅0从车站2的机票: 13公里,230円
- 駅2从车站4的机票: 14公里,230円
- 駅4从车站6的机票: 14公里,230円
胡桃先生是一个节俭的人,他想到了利用这种分票方式来节省交通费用。
狂三先生在车站 我想去S从车站G,但如果可以的话,我想分票以获得更便宜的票价。
然而,购买多张票对于狂三来说是一件麻烦事。
所以胡桃先生说, 我考虑过搬到最大2门票可用于 考虑移动到S从车站G。
因此,在上面的例子中,胡桃先生在车站。 如果您想移至0从车站6,710需要日元。
你的工作是狂三的车站。 目的是找出前往S从车站G所需的最低交通成本。
入力
N M K
S G
a_0 b_0 d_0
a_1 b_1 d_1
:
a_{M-1} b_{M-1} d_{M-1}
x_0 f_0
x_1 f_1
:
x_{K-1} f_{K-1}
- 1行显示车站数量。N, 路线数M,票价表尺寸K。 表示
- 2行包含出发车站的号码。S,到达站号 在G。 表示
- 3从行M+2行中,给出了路线信息。每条线路都有一个车站 连接距离a_i和 按字典顺序比较b_i表示存在d_i路由。 在
- M+3从行M+K+2行中,给出了票价表的信息。任何j\ (0≦j<K)和距离l\ (l≧1), 当我输入x_j≦l<x_{j+1},则距离l的票价是f_j。然而, 满足x_K是无限的。
制約
- 2≦N≦30000
- 1≦M≦60000
- 1≦K≦100
- 0≦S<N
- 0≦G<N
- S≠G
- 任何0≦i<M, 您可以获得0≦a_i<N,\ 0≦b_i<N,\ a_i≠b_i
- 任何0≦i<j<M, 您可以获得\{a_i,b_i\}≠\{a_j,b_j\}
- 任何0≦i<M, 您可以获得1≦d_i≦10^4
- 1=x_0<x_1<...<x_{K-1}≦10^9
- 1≦f_0<f_1<...<f_{K-1}≦10^9
- 駅S从车站G的路线
出力
部分点 1
- 2≦N≦100
- 1≦M≦200
- 分割机票不会让您的交通变得更便宜。 即车站 最好只购买S从车站G的机票 它比购买1件。
部分点 2
- 2≦N≦100
- 1≦M≦200
入力例 1
7 6 6 0 6 0 1 6 1 2 7 2 3 6 3 4 8 4 5 5 5 6 9 1 180 7 230 16 400 26 530 41 740 61 820
出力例 1
710
- 如问题正文所示。
入力例 2
7 6 6 4 1 0 1 6 1 2 7 2 3 6 3 4 8 4 5 5 5 6 9 1 180 7 230 16 400 26 530 41 740 61 820
出力例 2
400
- 路线和票价表与输入示例1相同,但出发和到达站不同。在这种情况下,车站 最好只买一张去4减去1的票。
入力例 3
5 5 4 0 4 0 1 2 1 2 3 2 4 5 1 3 8 3 4 6 1 100 4 200 9 400 16 600
出力例 3
300
- 从一个车站到另一车站可能有多条路线。
入力例 4
2 1 2 0 1 0 1 3 1 100 3 210
出力例 3
210