分数: 400 分
问题陈述
高桥正在城市的街道上漫步。该市有 N 交叉口,且交叉口之间由双向道路连接。有 共有 M 条路,每条路都有所需的行驶时间。多条道路可以连接同一对交叉路口,但没有道路将交叉路口连接到其自身(无自环路)。
该市有 K 收费站,每个都安装在不同的十字路口。的 j第一个收费站安装在路口 L_j,其通行费为 C_j。没有收费站的路口不收取通行费。
高桥想要从十字路口出发 1 到交叉路口 N。他通过道路从一个十字路口移动到另一个十字路口,并且他可能多次经过同一个十字路口或同一条道路。
高桥的路线表示为一系列交叉路口 v_0, v_1, v_2, \ldots, v_s (其中 v_0 = 1 和 v_s = N)。这里,每对连续的交点 v_{k-1} 和 v_k (1 \leq k \leq s) 必须由道路直接连接。
的 总成本 行程的 是以下两个组成部分的总和:
- 所经过道路的总行驶时间。也就是说,选择连接的道路的行驶时间总和 v_{k-1} 和 v_k 为 k = 1, 2, \ldots, s。如果同一条路经过多次,则算多次。
- 沿线路口收费站的通行费总额。也就是说,对于每个交叉点 v_0, v_1, \ldots, v_s,如果该路口有收费站,则增加其通行费。如果同一路口在路线中出现多次,则每次都收取费用。两者的起点(路口 1)和目的地(交叉路口 N)包括在内。
求高桥从交叉路口行驶的最低总成本 1 到交叉路口 N。保证交叉点 N 可从交叉路口到达 1.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 0 \leq K \leq N
- 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
- U_i \neq V_i (1 \leq i \leq M)
- 1 \leq W_i \leq 10^9 (1 \leq i \leq M)
- 1 \leq L_j \leq N (1 \leq j \leq K)
- 全部 L_j 是不同的 (1 \leq j \leq K)
- 1 \leq C_j \leq 10^9 (1 \leq j \leq K)
- 交叉口 N 可从交叉路口到达 1
- 所有输入值均为整数
输入
N M K U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M L_1 C_1 L_2 C_2 \vdots L_K C_K
- 第一行包含 N (交叉点的数量), M (道路数量),以及 K (收费站数量),以空格分隔。
- 从第 2 行到 (M + 1)第行,道路信息给出 M 行。
- 的 (1 + i)第行给出两个交点 U_i, V_i 由 i第条路及其行驶时间 W_i,用空格分隔。该路可双向通行。
- 从 (M + 2)第 行 (M + K + 1)第线,收费站信息已给出 K 行。
- 的 (M + 1 + j)-th 行给出交集 L_j 其中 j第一个收费站已安装及其通行费 C_j,以空格分隔。
- If K = 0,这部分不存在。
输出
打印高桥从交叉路口行驶的最低总成本 1 到交叉路口 N 在一行中。
示例输入 1
4 4 1 1 2 2 2 3 2 3 4 2 1 4 10 3 5
示例输出 1
10
示例输入 2
6 7 3 1 2 3 1 3 5 2 4 4 3 4 1 4 5 2 5 6 3 2 5 10 2 6 4 3 5 1
示例输出 2
15
示例输入 3
8 10 4 1 2 5 1 3 3 2 4 2 3 5 4 4 6 6 5 6 2 6 7 3 7 8 4 5 7 8 1 4 10 1 2 5 3 6 1 8 4
示例输出 3
26