分数: 433 分
问题陈述
一座城市有 N 位置,编号自 1 to N。有 M 双向道路连接地点,其中 i第条路连接位置 A_i 和位置 B_i 并采取 C_i 遍历时间。同一对位置之间可能有多条道路。
高桥是在这个城市工作的一名送货员。每天,他都会离开所在地 1,即配送中心,访问多个配送目的地,然后返回地点 1.
今天, K 交货目的地 V_1, V_2, \ldots, V_K 已指定(位置 1 不包含在目的地中)。高桥必须离开地点 1,访问全部 K 每个目的地至少一次,然后返回地点 1。在旅行期间,他可以多次经过同一位置或同一条道路,但每次经过一条道路时,其旅行时间都会添加到总时间中。
求该路线的最短总行程时间。
约束
- 2 \leq N \leq 5 \times 10^4
- 1 \leq M \leq 5 \times 10^4
- 1 \leq K \leq 15
- 2 \leq V_i \leq N (1 \leq i \leq K)
- 全部 V_i 是不同的
- 1 \leq A_i, B_i \leq N, A_i \neq B_i (1 \leq i \leq M)
- 同一对位置之间可能有多条道路
- 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
- 从该位置可到达所有目的地 1
- 所有输入值均为整数
输入
N M K V_1 V_2 \ldots V_K A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
- 第一行包含位置数 N, 道路数量 M,以及目的地数量 K,用空格分隔。
- 第二行包含 K 目的地号码 V_1, V_2, \ldots, V_K,用空格分隔。
- 以下 M 行各包含,对于 i第行 (1 \leq i \leq M),两个位置 A_i, B_i 由 i第条路及行车时间 C_i ,以空格分隔。
输出
在一行中打印从该位置出发的路线的最短总行程时间 1,访问所有 K 每个目的地至少一次,并返回该位置 1.
示例输入 1
4 5 2 2 3 1 2 2 2 3 3 3 1 4 1 4 10 4 3 1
示例输出 1
9
示例输入 2
5 8 2 3 5 1 2 1 2 3 1 1 3 10 1 3 3 1 4 2 4 5 2 3 5 100 2 5 5
示例输出 2
12
示例输入 3
8 12 3 4 6 8 1 2 2 2 3 2 3 4 2 1 5 3 5 6 3 6 7 3 7 8 3 4 8 4 2 5 2 3 6 2 4 7 2 1 8 20
示例输出 3
22
示例输入 4
14 22 5 4 7 9 12 14 1 2 4 2 3 3 3 4 5 4 5 2 5 6 4 6 7 3 7 8 6 8 9 2 9 10 4 10 11 3 11 12 5 12 13 2 13 14 4 1 5 7 2 6 6 4 8 5 5 9 8 7 11 4 9 13 3 3 10 12 6 12 9 1 14 30
示例输出 4
51
示例输入 5
16 15 15 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 1 1 3 2 1 4 3 1 5 4 1 6 5 1 7 6 1 8 7 1 9 8 1 10 9 1 11 10 1 12 11 1 13 12 1 14 13 1 15 14 1 16 1000000000
示例输出 5
2000000210