← 返回题目列表

AtCoder · awc0050_d

D. 城市步行和通行费

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

分数: 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