H - Caretaker
Assam
2
s
1024
MB
300
点
問題文
お茶大には $N$ 匹の猫がいて、お茶猫と呼ばれています。
お茶猫のお世話がかりになった花子さんは、$N$ 箇所を巡り全ての猫にご飯をあげます。
最初、花子さんは $1$ 匹目の猫の地点にいます。なるべく短い距離で全ての猫にご飯をあげたいです。
$2$ 匹目以降はどの順番で訪ねても良いですが、猫がご飯を期待してしまうので、同じ猫の地点は2回通ってはいけません。
猫 $i$ と猫 $j$ の間の距離は 整数$V_{ij}$ として与えられます。
$N$ 匹目の猫にご飯を与え終わった時に、移動した距離の総和の最小値はいくつになるでしょうか。
(2024/11/09 10:38 追記 ) 距離の総和の最小値を出力する旨を追記しました。
(2024/11/09 10:59 追記 ) $V_{ij}$ についての条件を追記しました。
制約
- $N, V_{ij}$ は整数
- $1< N\leq 11$
- $1\leq V_{ij}\leq 2\times 10^5\quad(i\neq j)$
- $V_{ii}=0$
- $V_{ij} = V_{ji}$
入力
入力は以下の形式で与えられます。
$N$
$V_{11}\quad V_{12}\cdots V_{1N}$
$\qquad\quad\vdots$
$V_{N1}\quad V_{N2}\cdots V_{NN}$
出力
答えを一行で出力してください。
入力例 1
4
0 10 20 10
10 0 40 20
20 40 0 30
10 20 30 0
出力例 1
60
1→2→4→3の順で訪ねることで、$10+20+30=60$ を達成できます。
入力例 2
11
0 2 9 88 44 81 18 73 98 17 17
2 0 9 79 42 15 60 63 50 22 40
9 9 0 9 85 92 7 53 68 77 61
88 79 9 0 98 22 22 60 79 52 76
44 42 85 98 0 58 60 68 29 62 15
81 15 92 22 58 0 79 11 10 17 73
18 60 7 22 60 79 0 72 62 24 39
73 63 53 60 68 11 72 0 64 17 8
98 50 68 79 29 10 62 64 0 68 49
17 22 77 52 62 17 24 17 68 0 7
17 40 61 76 15 73 39 8 49 7 0
出力例 2
131