← 返回题目列表

AtCoder · awc0021_d

D. 检查站拉力赛

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

分数: 400 分

问题陈述

高桥正在参加定向比赛。在本次比赛中,他必须按顺序通过指定的检查站并到达目标。

比赛场地有 N 位置,编号自 1 to N。有 M 这些位置之间的双向道路。的 i第路 (1 \leq i \leq M) 连接位置 U_i 和位置 V_i,并采取 任一方向行驶 T_i 分钟。可能有多条道路连接同一对位置。此外,不保证所有地点都可以通过道路到达。

高桥目前位于该位置 1,起点。根据比赛规则,他必须参观 K 指定检查站 P_1, P_2, \ldots, P_K 按照这个顺序,终于到达地点 N,目标。具体来说,他离开地点 1 并到达位置 P_1,然后到达位置 P_2, \ldots,到达位置 P_K,终于到达地点 N.

有关检查站访问的规则如下:

  • 检查点仅按顺序完成 P_1, P_2, \ldots, P_K。当到达某个位置时,如果该位置是下一个要访问的检查点,则立即完成对该检查点的访问。除行程时间外,不会产生任何时间。
  • 由于高桥从该位置开始 1,如果 P_1 = 1,访问检查站 P_1 在出发时完成。一般来说,当一个检查点访问完成后,如果下一个要访问的检查点与当前位置相同,则该检查点的访问也立即完成。
  • 即使你经过了尚未轮到的检查点位置,该检查点也没有完成。轮到您时,您必须已经到达该位置,或者重新访问该位置。
  • 指定的检查点编号不一定彼此不同,并且可能与位置一致 1 或位置 N.

在整个旅程中,您可能会多次经过同一个地点或同一条道路。

由于高桥的目标是获胜,所以他希望在最短的时间内达到目标。查找从该地点出发的最短总行程时间(以分钟为单位) 1,访问 按顺序 P_1, P_2, \ldots, P_K ,然后到达地点 N。如果不存在有效路由,则输出 -1.

约束

  • 2 \leq N \leq 5 \times 10^4
  • 1 \leq M \leq 10^5
  • 1 \leq K \leq 10
  • 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 T_i \leq 10^9 (1 \leq i \leq M)
  • 1 \leq P_j \leq N (1 \leq j \leq K)
  • 的 P_j 值不一定不同
  • 图不一定相连
  • 所有输入值均为整数

输入

N M K
U_1 V_1 T_1
U_2 V_2 T_2
\vdots
U_M V_M T_M
P_1 P_2 \ldots P_K
  • 第一行包含位置数 N, 道路数量 M,以及要访问的检查点数量 K,以空格分隔。
  • 以下 M 行每行包含整数 U_i, V_i, T_i 以空格分隔,表示 i第路 (1 \leq i \leq M) 双向连接位置 U_i 和位置 V_i 并采取 穿越 T_i 分钟。
  • 最后一行包含 K 检查点编号 P_1, P_2, \ldots, P_K 以空格分隔。必须按此顺序访问它们。

输出

在单行中输出从位置出发的最小总行程时间(以分钟为单位) 1,访问 按顺序 P_1, P_2, \ldots, P_K 按顺序,并到达地点 N。如果不存在有效路由,则输出 -1.

请注意,答案可能会超过 10^{10}.


示例输入 1

5 6 2
1 2 3
2 3 4
3 5 2
1 4 10
4 5 1
2 4 5
3 4

示例输出 1

11

示例输入 2

4 3 1
1 2 5
2 3 3
3 4 7
2

示例输出 2

15

示例输入 3

10 15 4
1 2 2
1 3 5
2 3 1
2 4 4
3 5 3
4 5 2
4 6 6
5 6 1
5 7 8
6 8 3
7 8 2
7 9 4
8 9 1
8 10 5
9 10 2
3 6 8 9

示例输出 3

13