← 返回题目列表

AtCoder · awc0029_e

E. 旅行送货

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

分数: 433 分

问题陈述

高桥是一名送货员。他指定的区域有 N 位置,从位置开始编号 1 到位置 N。有 M 地点之间的单向道路,以及 i第路 (1 \leq i \leq M) 只能从位置遍历 U_i 到位置 V_i,正成本为 W_i。高桥仅使用这些道路在不同地点之间移动。

高桥目前在位于以下位置的办公室 S。作为今天的任务,他需要将包裹递送至 K 目的地 T_1, T_2, \ldots, T_K。这些目的地彼此不同且位置不同 S.

高桥出发地点 S,访问所有 K 目的地 以他喜欢的任何顺序 交付包裹,最后必须返回所在地点的办公室 S。在这里,高桥的路线是从位置开始的一系列道路 S,一条一条地遍历道路(使得每条道路的终点与下一条道路的起点相匹配),最终回到位置 S。只要高桥在从出发到返回的路线中至少经过该目的地一次,即视为已送达该目的地。即,仅经过目的地位置就足够了。

旅途中,允许多次穿越同一条道路或访问同一地点。但是,如果多次经过同一条路,则每次都会产生费用。

求高桥从所在位置出发的所有可能路线中所经过的道路的最小总成本(其中多次经过的道路的成本将在每次遍历中计算) S,访问所有 K 目的地,然后返回位置 S。如果无法访问所有目的地并返回所在地 S,输出 -1.

约束

  • 2 \leq N \leq 300
  • 1 \leq M \leq N(N-1)
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 没有两条道路具有相同的起点和终点 (U_i, V_i) (无平行边)
  • 1 \leq W_i \leq 10^6
  • 1 \leq S \leq N
  • 1 \leq K \leq 15
  • 1 \leq T_j \leq N (1 \leq j \leq K)
  • 全部 T_j 是不同的
  • T_j \neq S (1 \leq j \leq K)
  • 所有输入值均为整数

输入

N M
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
S K
T_1 T_2 \ldots T_K
  • 第一行包含位置数 N 和道路数量 M,用空格分隔。
  • 以下 M 行各包含,对于 i第路 (1 \leq i \leq M),起点 U_i,终点 V_i,以及成本 W_i,用空格分隔。
  • 下一行包含高桥的起始位置 S 和目的地数量 K,用空格分隔。
  • 下一行包含目标位置 T_1, T_2, \ldots, T_K,用空格分隔。

输出

单行输出高桥访问所有目的地并返回所在位置所经过的道路的最小总成本 S。如果无法访问所有目的地并返回所在地 S,输出 -1.


示例输入 1

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

示例输出 1

9

示例输入 2

3 2
1 2 1
2 3 1
1 1
2

示例输出 2

-1

示例输入 3

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

示例输出 3

20

示例输入 4

10 20
1 2 4
2 3 3
3 4 5
4 5 2
5 6 7
6 7 1
7 8 6
8 9 3
9 10 4
10 1 8
1 5 20
5 1 15
2 6 10
6 2 12
3 7 8
7 3 9
4 8 6
8 4 7
1 3 11
9 1 5
1 5
2 4 6 8 10

示例输出 4

43

示例输入 5

2 2
1 2 1000000
2 1 1000000
1 1
2

示例输出 5

2000000