AT_qupc2014_d.切符分割

QU 铁道是一家拥有 $N$ 个车站和 $M$ 条线路的铁路公司。
每个车站都被分配了一个从 $0$ 到 $N-1$ 的唯一编号。
每条线路连接两个不同的车站，并且可以双向通行。
此外，QU 铁道采用分段计价的票价表，票价会根据距离的不同而变化。
从某个车站 A 到另一个车站 B 的单程票价，由 A 到 B 的最短距离决定，并根据票价表确定。

例如，考虑如下的线路图和票价表。

距离（km） 票价（円）
$1$ km - $6$ km：$180$ 円
$7$ km - $15$ km：$230$ 円
$16$ km - $25$ km：$400$ 円
$26$ km - $40$ km：$530$ 円
$41$ km - $60$ km：$740$ 円
$61$ km 及以上：$820$ 円

在这个例子中，考虑从车站 $0$ 到车站 $6$ 的票价。
从车站 $0$ 到车站 $6$ 的最短距离为 $41$ km，因此根据票价表，从 $0$ 到 $6$ 的单程票价为 $740$ 円。

在 QU 铁道中，也可以通过购买多张覆盖不同区间的车票，从一个车站到另一个车站，这被称为“分割购票”。
例如，持有以下两张车票，也可以从 $0$ 到 $6$：

• $0$ 到 $1$ 的车票：$6$ km，$180$ 円
• $1$ 到 $6$ 的车票：$35$ km，$530$ 円

此时总票价为 $180+530=710$ 円，比直接购买 $0$ 到 $6$ 的单程票更便宜。
像这样，通过分割购票，有时可以节省交通费用。

进一步地，考虑使用 $3$ 张车票从 $0$ 到 $6$：

• $0$ 到 $2$ 的车票：$13$ km，$230$ 円
• $2$ 到 $4$ 的车票：$14$ km，$230$ 円
• $4$ 到 $6$ 的车票：$14$ km，$230$ 円

此时总票价为 $230+230+230=690$ 円，比前面的方法还要便宜。

节俭的胡桃小姐希望通过巧妙地分割购票来节省交通费用。
她想从车站 $S$ 前往车站 $G$，如果可能的话，希望通过分割购票来降低票价。
但购买太多车票对她来说很麻烦。
因此，胡桃小姐决定最多只使用 $2$ 张车票，从 $S$ 到 $G$。
所以在上述例子中，胡桃小姐从 $0$ 到 $6$ 需要 $710$ 円。

你的任务是，计算胡桃小姐从 $S$ 到 $G$ 最少需要多少交通费用（最多使用 $2$ 张车票）。
输入格式如下：

$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$ 行，每行描述一条线路，表示有一条长度为 $d_i$ 的线路连接 $a_i$ 和 $b_i$。
• 第 $M+3$ 行到第 $M+K+2$ 行，每行描述票价表。对于任意 $j\ (0\leq j<K)$ 和距离 $l\ (l\geq 1)$，如果 $x_j\leq l < x_{j+1}$，则距离 $l$ 的票价为 $f_j$。其中 $x_K$ 视为无穷大。

输入中的所有变量均为整数，并满足以下约束条件：

• $2\leq N\leq 30000$
• $1\leq M\leq 60000$
• $1\leq K\leq 100$
• $0\leq S<N$
• $0\leq G<N$
• $S\neq G$
• 对任意 $0\leq i<M$，$0\leq a_i<N,\ 0\leq b_i<N,\ a_i\neq b_i$
• 对任意 $0\leq i<j<M$，$\{a_i,b_i\}\neq\{a_j,b_j\}$
• 对任意 $0\leq i<M$，$1\leq d_i\leq 10^4$
• $1=x_0<x_1<\cdots<x_{K-1}\leq 10^9$
• $1\leq f_0<f_1<\cdots<f_{K-1}\leq 10^9$
• 存在从 $S$ 到 $G$ 的路径

请输出最多购买 $2$ 张车票时，从 $S$ 到 $G$ 的最小总票价。输出时请在末尾添加换行符。

满足以下 $3$ 个条件的测试点可得 $20$ 分：

• $2\leq N\leq 100$
• $1\leq M\leq 200$
• 分割购票不会更便宜，即直接买 $S$ 到 $G$ 的单程票最优。

满足以下 $2$ 个条件的测试点可得 $20$ 分：

• $2\leq N\leq 100$
• $1\leq M\leq 200$

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

710

• 如题面所示。

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

400

• 与样例 1 路线和票价表相同，但出发站和到达站不同。这种情况下，直接买 $4$ 到 $1$ 的单程票最优。

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

300

• 从某个车站到另一个车站可能存在多条路径。

2 1 2
0 1
0 1 3
1 100
3 210

210

第 $1$ 行：$N$ $M$ $K$
第 $2$ 行：$S$ $G$
第 $3$ 行到第 $M+2$ 行：每行 $a_i$ $b_i$ $d_i$
第 $M+3$ 行到第 $M+K+2$ 行：每行 $x_j$ $f_j$

输出从 $S$ 到 $G$ 最少需要的票价（最多使用 $2$ 张车票），末尾需换行。

无。

由 ChatGPT 4.1 翻译