← 返回题目列表

AtCoder · qupc2014_d

D. 切符分割

中文机器翻译题面 查看原题

問題文

QU铁路是N站和M线路。
在每个车站, 分配的唯一站号最多为0减去N-1。
每条路线都不同2它连接两个车站,可用于任一方向行驶。
QU铁路也使用票价表,根据距离分阶段改变票价。
从 A 站到 B 站的车票价格是根据 A 站到 B 站的最短距离从票价表中确定的。

例如,请考虑以下路线图和票价表。
距離運賃
1 公里- 6 km180 円
7 公里- 15 km230 円
16 公里- 25 km400 円
26 公里- 40 km530 円
41 公里- 60 km740 円
61 公里或以上820 円

在此示例中,该站0从车站6的票价。 到
駅0从车站6的总距离是41公里,所以 从票价表来看,车站 前往0从车站6的机票是740变成日元。

QU 铁路还允许您使用不同路段的多张车票从一个车站前往另一个车站。
这称为票证拆分。
例如,以下2如果您有一张票,您可以 您可以向上移动到0从车站6。
  • 駅0从车站1的机票: 6公里,180円
  • 駅1从车站6的机票: 35公里,530円
此时的总票价为180+530=710变成日元, 车站 前往0从车站6的机票 它比购买1床单便宜。
这样一来,在QU铁路上,存在通过分票来降低票价的情况。

另外,如下:3门票可用于 考虑移动到0从车站6的情况。
  • 駅0从车站2的机票: 13公里,230円
  • 駅2从车站4的机票: 14公里,230円
  • 駅4从车站6的机票: 14公里,230円
此时的总票价为230+230+230=690日元,变得更加便宜。

胡桃先生是一个节俭的人,他想到了利用这种分票方式来节省交通费用。
狂三先生在车站 我想去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的路线

出力

最大票数 购买2车票时的车站 到S从车站G的总票价最小值为 在1行输出。输出末尾必须有换行符。

部分点 1

下面3如果您正确回答了满足以下约束的测试用例, 可获得20积分。
  • 2≦N≦100
  • 1≦M≦200
  • 分割机票不会让您的交通变得更便宜。 即车站 最好只购买S从车站G的机票 它比购买1件。

部分点 2

下面2如果您正确回答了满足以下约束的测试用例, 可获得20积分。
  • 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