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