問題一覧 > 通常問題

No.3158 Collect Stamps

レベル : / AI推定難易度 : 1050 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 90
作問者 : kmmtkm / テスター : jastaway fluorine 👑 みうね tatesoto 👑 kencho TKTYI butsurizuki
お気に入りにしたユーザー ProblemId : 12234 / 自分の提出
問題文最終更新日: 2025-05-23 19:00:52
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
KCPC新歓杯 -Happy Birthday physics0523- (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。