← 返回题目列表

AtCoder · awc0044_d

D. 优化配送路线

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

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