M - Real Traveling Salesman

Contest Duration: 2020-05-23(Sat) 04:00 - 2020-05-23(Sat) 09:00 (local time) (300 minutes) Back to Home

M - Real Traveling Salesman Editorial

Time Limit: 2.5 sec / Memory Limit: 1024 MB

配点 : $6$ 点

注意

この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

スーヌケ王国には $N$ 個の街があります。

王国には $M$ 本の道が存在していて、 $i$ 番目の道は、街 $u_i$ , $v_i$ を双方向に繋いでいます。ある道を $1$ 回利用するためには、通行料として $1$ 円を払う必要があります。任意の街から出発して、いくつかの道を経由することで任意の街に辿り着けることが分かっています。

王国の行商人であるタカーハ氏は現在街 $s$ にいて、これから $K$ 個の街 $t_1, t_2, \ldots, t_K$ で取引をしたいと思っています。

街 $s$ から出発して $K$ 個の街それぞれを少なくとも $1$ 回は訪れるために、タカーハ氏が払う必要のある通行料の合計は最小で何円でしょうか。最終的に街 $s$ に戻ってくる必要はありません。

同じ道を複数回利用するとき、その都度通行料を払う必要があることに注意してください。

制約

入力は全て整数である。
$2 \leq N \leq 10^5$
$N - 1 \leq M \leq 10^5$
$1 \leq u_i < v_i \leq N$
$i \neq j$ のとき $(u_i, v_i) \neq (u_j, v_j)$
$1 \leq s \leq N$
$1 \leq K \leq \min (N - 1, 16)$
$1 \leq t_i \leq N$
$i \neq j$ のとき $t_i \neq t_j$
$s \neq t_i$

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $M$ 
 $u_1$   $v_1$ 
 $u_2$   $v_2$ 
 $\vdots$ 
 $u_M$   $v_M$ 
 $s$ 
 $K$ 
 $t_1$   $t_2$   $\ldots$   $t_K$

出力

タカーハ氏が払う必要のある通行料の合計の最小値を整数として出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

まず街 $2$ から街 $1$ に移動して、その後再び街 $2$ へと戻り、次に街 $3$ へと移動することで、合計 $3$ 円の通行料で街 $1$ と街 $3$ を訪れることができます。

入力例 2Copy

Copy

出力例 2Copy

Copy

Score : $6$ points

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

The Kingdom of Soonuke has $N$ towns.

There are $M$ roads in the kingdom. The $i$ -th road connects Town $u_i$ and $v_i$ bidirectionally. You need to pay the toll of $1$ yen each time you use a road. We know that any town can be reached from any town by using some number of roads.

Takaaha, a merchant, is now at Town $s$ and wants to make transactions in $K$ towns $t_1, t_2, \ldots, t_K$

What is the minimum total toll Takaaha needs to pay when he starts at Town $s$ and visit each of the $K$ towns at least once? He does not need to come back to Town $s$ in the end.

Note that using the same road multiple times will cost you the toll that number of times.

Constraints

All values in input are integers.
$2 \leq N \leq 10^5$
$N - 1 \leq M \leq 10^5$
$1 \leq u_i < v_i \leq N$
If $i \neq j$ , $(u_i, v_i) \neq (u_j, v_j)$ .
$1 \leq s \leq N$
$1 \leq K \leq \min (N - 1, 16)$
$1 \leq t_i \leq N$
If $i \neq j$ , $t_i \neq t_j$ .
$s \neq t_i$

Input

Input is given from Standard Input in the following format:

 $N$   $M$ 
 $u_1$   $v_1$ 
 $u_2$   $v_2$ 
 $\vdots$ 
 $u_M$   $v_M$ 
 $s$ 
 $K$ 
 $t_1$   $t_2$   $\ldots$   $t_K$

Output

Print the minimum total toll Takaaha needs to pay, as an integer.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

If we go from Town $2$ to Town $1$ , then go back to Town $2$ , then go to Town $3$ , we can visit the towns $1$ and $3$ with the total toll of $3$ yen.

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy