AT_past202005_m.行商計画問題

题目简述

给出一张 $n$ 点 $m$ 边的无向图，所有点互相可达。第 $i$ 条边连接点 $u_i$ 和点 $v_i$。每次使用一条边都会增加 $1$ 点代价。求出从点 $s$ 出发，至少访问 $t_1,t_2,...,t_k$ 这 $k$ 个点各一次的最小代价点数。最终不需要回到点 $s$。

第一行：$n,m$

接下来 $m$ 行：第 $i$ 行为 $u_i,v_i$

接下来一行：$s$

接下来一行：$k$

接下来一行：$t_1,t_2,...,t_k$

一个整数，最小代价点数。

数据约束

• 输入均为整数；
• $2 \le n \le 10^5$，$n-1 \le m \le 10^5$；
• $1 \le u_i \lt v_i \le n$，且任意两对 $(u_i,v_i)$ 互不相同；
• $1 \le s \le n$，$1 \le k \le \min(n-1,16)$；
• $1 \le t_i \le n$，任意两对 $t_i$ 互不相同，$s$ 与任意一个 $t_i$ 都不同。