分数: 400 分
问题陈述
高桥是一家送货公司的司机。今天,他必须从指定地点投递包裹 1,仓库所在位置,指向 N,交货目的地。
点的编号为 1 to N,并且有 M 连接各点的道路。每条道路也编号为 1 to M。道路 i (1 \leq i \leq M) 双向连接点 U_i 和点 V_i,正常行程时间为 W_i 分钟。可能有多条道路连接同一对点。
然而,由于今天道路施工, K 道路受到速度限制。限速道路数量为 C_1, C_2, \ldots, C_K。限速道路仍可通行,但行车时间变长 2 倍正常时间,即 2W_i 分钟。不受速度限制的道路的正常行驶时间为 W_i 分钟。
求高桥从点出发的最短时间(以分钟为单位) 1 来点 N。如果无法到达点 N 从点 1,输出 -1.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 0 \leq K \leq M
- 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 C_j \leq M (1 \leq j \leq K)
- C_1, C_2, \ldots, C_K 都是不同的
- 所有输入值均为整数
输入
N M K U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M C_1 C_2 \ldots C_K
- 第一行包含整数 N 代表点数,整数 M 代表道路数量,整数 K 表示限速的道路数量,以空格分隔。
- 的 (1 + i)第行 (1 \leq i \leq M) 包含点 U_i, V_i 有公路相连 i 和正常行驶时间 W_i,用空格分隔。
- 当 K \geq 1, (M + 2)第行包含限速道路的编号 C_1, C_2, \ldots, C_K,用空格分隔。当 K = 0,未给出此行(输入结束于 (M+1)第行)。
输出
在一行中输出高桥从点出发的最短时间(以分钟为单位) 1 来点 N。如果无法到达点 N,输出 -1.
示例输入 1
4 5 1 1 2 3 1 3 2 2 4 5 3 4 4 2 3 7 3
示例输出 1
6
示例输入 2
3 1 0 1 2 5
示例输出 2
-1
示例输入 3
8 12 3 1 2 4 1 3 7 2 3 2 2 4 5 3 5 3 4 5 1 4 6 8 5 6 6 5 7 9 6 8 3 7 8 2 3 7 10 1 6 11
示例输出 3
19
示例输入 4
15 20 5 1 2 10 1 3 15 2 4 12 3 4 8 3 5 7 4 6 6 5 6 9 5 7 3 6 8 14 7 8 5 7 9 11 8 10 4 9 10 2 9 11 13 10 12 7 11 12 6 11 13 8 12 14 3 13 14 10 14 15 5 2 5 7 9 19
示例输出 4
71
示例输入 5
2 1 1 1 2 1000000000 1
示例输出 5
2000000000
示例输入 6
4 5 1 1 2 3 1 3 2 2 4 5 3 4 4 2 3 7 3
示例输出 6
6
示例输入 7
3 1 0 1 2 5
示例输出 7
-1
示例输入 8
8 12 3 1 2 4 1 3 7 2 3 2 2 4 5 3 5 3 4 5 1 4 6 8 5 6 6 5 7 9 6 8 3 7 8 2 3 7 10 1 6 11
示例输出 8
19
示例输入 9
15 20 5 1 2 10 1 3 15 2 4 12 3 4 8 3 5 7 4 6 6 5 6 9 5 7 3 6 8 14 7 8 5 7 9 11 8 10 4 9 10 2 9 11 13 10 12 7 11 12 6 11 13 8 12 14 3 13 14 10 14 15 5 2 5 7 9 19
示例输出 9
71
示例输入 10
2 1 1 1 2 1000000000 1
示例输出 10
2000000000