← 返回题目列表

AtCoder · awc0070_e

E. 送货员回合

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

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