No.3158 Collect Stamps
Problem Statement
Butsuri-zuki-kun is about to take part in a stamp rally.
There are $N$ places numbered from $1$ to $N$, each with a different stamp, and
collecting $M$ or more distinct stamps among them earns the right to receive a prize.
However, the prize can be received only at the $K$ places $A_{1}, \dots, A_{K}$.
Moving from place $i$ to place $j$ takes time $T_{i, j}$.
$T_{i, j}$ satisfies the following $3$ conditions.
- $T_{i, i} = 0 \ (1 \leq i \leq N)$
- $1 \leq T_{i, j} \leq 10^{5} \ (1\leq i, j \leq N, i \ne j)$
- $T_{i, j} \leq T_{i, k} + T_{k, j} \ (1 \leq i, j, k \leq N)$
You may freely choose the place where you start the stamp rally. Find the minimum time required until you receive the prize.
Note that you can also get stamps at the place where you start the stamp rally and at the place where you receive the prize.
Also, only the time spent moving needs to be considered; the time to get stamps and the time to receive the prize can be ignored.
Constraints
- All inputs are integers
- $1 \leq N \leq 16$
- $1 \leq M \leq \min(N, 5)$
- $1 \leq K \leq N$
- $1 \leq A_{1} < A_{2} < \dots < A_{K} \leq N$
- $T_{i, i} = 0 \ (1 \leq i \leq N)$
- $1 \leq T_{i, j} \leq 10^{5} \ (1\leq i, j \leq N, i \ne j)$
- $T_{i, j} \leq T_{i, k} + T_{k, j} \ (1 \leq i, j, k \leq N)$
Input
$N\ M \ K$
$A_{1} \ \dots \ A_{K}$
$\begin{matrix}
T_{1, 1} & \dots & T_{1, N} \\
\vdots & \ddots & \vdots \\
T_{N, 1} & \dots & T_{N, N}
\end{matrix}$
Output
Output the minimum time required until you receive the prize.
Sample
Sample 1
Input
3 2 1 3 0 1 1 1 0 1 1 1 0
Output
1
For example, by starting the stamp rally at place $2$ and moving from place $2$ to place $3$,
you can collect $2$ stamps and receive the prize at place $3$.
The time required until receiving the prize in this case is $1$.
Note that you can also collect stamps at the place where you start the stamp rally and at the place where you receive the prize.
The time required until receiving the prize cannot be made less than $1$, so output 1.
Sample 2
Input
5 1 3 1 2 5 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0
Output
0
If you start the stamp rally at place $1$, you can receive the prize without moving.
Sample 3
Input
5 3 4 1 2 4 5 0 4 4 7 2 7 0 7 6 9 4 7 0 4 6 1 4 5 0 3 6 2 4 5 0
Output
3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
jastaway
butsurizuki