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

第 $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 翻译