分数: 433 分
问题陈述
高桥是一名送货司机,每天给顾客送货。
高桥负责的区域包括 N 交叉路口和 M 道路。交叉点的编号从 1 to N.The i第路 (1 \leq i \leq M) 双向连接交叉口 U_i 和交叉路口 V_i,并且需要 W_i 分钟向任一方向移动。可能有多条道路连接同一对交叉路口。
今天有 K 交付请求。的 j第一个请求 (1 \leq j \leq K) 需要将包裹交付给十字路口的客户 D_j。全部 K 配送目的地路口不同,并且没有一个与路口相同 S 办公室所在地。高桥必须从十字路口出发 S 办公室所在位置,访问所有 K 送货目的地,然后返回路口 S。他可以自由选择访问送货目的地的顺序。他在旅行期间可能多次经过同一个十字路口或同一条道路。
高桥经过该十字路口时,即使正在前往另一个目的地,也会自动完成向该目的地的配送。换句话说,如果他在前往另一个目的地的同时经过一个配送目的地,则也完成了对该目的地的配送。交付包裹的时间可以忽略不计。
求完成所有送货并返回办公室所需的最短总行程时间(以分钟为单位)。
保证所有配送目的地均可从路口到达 S (由于道路是双向的,因此也可以从每个送货目的地返回交叉路口 S).
约束
- 2 \leq N \leq 10\,000
- 1 \leq M \leq 20\,000
- 1 \leq U_i, V_i \leq N
- U_i \neq V_i
- 1 \leq W_i \leq 10^6
- 1 \leq S \leq N
- 1 \leq K \leq 15
- 1 \leq D_j \leq N
- 全部 D_j 是不同的
- D_j \neq S
- 所有交货目的地均可从 S
- 所有输入值均为整数
输入
N M U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M S K D_1 D_2 \ldots D_K
- 第一行包含交叉点的数量 N 和道路数量 M,用空格分隔。
- 以下 M 行各包含,对于 i第路 (1 \leq i \leq M),两个交叉点的数量 U_i, V_i 连接道路和出行时间 W_i (以分钟为单位),以空格分隔。
- 下一行包含交叉点编号 S 办事处所在地及交货数量 K,用空格分隔。
- 下一行包含 K 配送目的地路口号码 D_1, D_2, \ldots, D_K,用空格分隔。
输出
在单行中以整数形式输出访问所有送货目的地并返回办公室的最小总行程时间(以分钟为单位)。
样本输入 1
4 5 1 2 2 2 3 3 3 4 4 1 4 7 1 3 10 1 2 3 4
示例输出 1
16
示例输入 2
6 8 1 2 3 1 3 5 2 3 1 2 4 7 3 5 4 4 5 2 4 6 3 5 6 6 1 3 4 5 6
示例输出 2
26
示例输入 3
10 14 1 2 5 1 3 12 2 3 4 2 4 8 3 5 3 4 5 6 4 6 2 5 7 7 6 7 4 6 8 9 7 9 3 8 9 5 8 10 2 9 10 6 1 5 3 5 7 9 10
示例输出 3
54