問題一覧 > 通常問題

No.1284 Flip Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 65
作問者 : platinumplatinum / テスター : 37zigen37zigen
6 ProblemId : 5079 / 出題時の順位表
問題文最終更新日: 2020-11-17 08:47:33

問題文

$N$ 個のマスがあり、それぞれ $1, 2, \dots, N$ と番号が振られています。
各マスには片面が赤、もう片面が白のカードが一枚置いてあり、最初は全て赤が表になっています。
A君はカードを一枚ずつ裏返して全て白が表になっている状態にしたいと思いましたが、赤色が好きなB君はこれを邪魔します。
二人は以下のように行動します。

0. はじめにA君が好きなマスを $1$ つ選び、カードを裏返して白を表にする。

1. A君は赤が表になっているマスから $1$ つ選び、カードを裏返して白を表にする。
この時に選んだマスを $q$ 、一つ前に選んだマスを $p$ としたとき、コスト $c_{p,q} (>0)$ がかかる。

2. B君は、A君が一つ前に選んだマス $p$ のカードを裏返し、赤を表にする。
ただし、それ以前にマス $p$ のカードを裏返したことがある場合は何もしない。

3. 1. 2. を繰り返す。全てのカードが白であり、かつB君が何もしなかった時点でゲームを終了する。


ただし、必ずしも $c_{i,j}=c_{j,i}$ とは限りません。また、$c_{i,i}=0$ とします。
ゲーム終了までにかかるコストの総和の最小値を求めてください。

入力

$N$
$c_{1,1}$ $c_{1,2}$ $\dots$ $c_{1,N}$
$c_{2,1}$ $c_{2,2}$ $\dots$ $c_{2,N}$
$\vdots$
$c_{N,1}$ $c_{N,2}$ $\dots$ $c_{N,N}$

・入力は全て整数である。
・$2 \le N \le 9$
・$c_{i,i} = 0$
・$1 \le c_{i,j} \le 10^8$ $(i \neq j)$

出力

ゲーム終了までにかかるコストの総和の最小値を出力してください。

サンプル

サンプル1
入力
2
0 10
20 0
出力
40

マス $1$ → $2$ → $1$ → $2$ の順にカードを裏返すのが最適です。
このときコストの総和は、$10+20+10=40$ となります。

サンプル2
入力
3
0 7 3
9 0 2
6 5 0
出力
15

マス $2$ → $3$ → $2$ → $3$ → $1$ の順にカードを裏返すのが最適です。
この時点で全てのカードが白でありかつB君は何もしないため、ゲームは終了します。
このように必ずしも全てのカードを二度裏返す必要はないことに注意してください。

サンプル3
入力
6
0 15024 31317 93469 62177 4320
49893 0 44972 34509 76317 68434
45883 5950 0 24246 41070 55112
86178 14298 54193 0 38052 3009
59166 59527 55171 91031 0 1398
88688 30894 42756 4816 93098 0
出力
193095

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。