C - 巡回セールスマン問題 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

N 個の都市があり、0, 1, …, N-1 と番号付けられている。全ての異なる 2 都市の間には道が存在し、都市 i から都市 j に移動するときのコストはA_{i,j} である。

あなたは今都市 0 にいる。ここから都市 0 以外の都市をちょうど 1 回ずつ訪れ、都市 0 に戻ってくる経路を作りたい。そのような経路における合計コストの最小値を求めよ。

制約

  • 2 \leq N \leq 13
  • i \neq j のとき、1 \leq A_{i, j} \leq 10^9
  • A_{i, i} = 0
  • 入力はすべて整数である。

入力

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

N
A_{0, 0} A_{0, 1} ... A_{0, N-1}
A_{1, 0} A_{1, 1} ... A_{1, N-1}
:
A_{N-1, 0} A_{N-1, 1} ... A_{N-1, N-1}

出力

都市 0 からスタートし、都市 0 以外の都市をちょうど 1 回ずつ訪れ、都市 0 に戻ってくる経路における合計コストの最小値を求めよ。

入力例 1

4
0 3 1 4
1 0 5 9
2 6 0 5
3 5 8 0

出力例 1

12

都市 0 \to 2 \to 3 \to 1 \to 0 と移動すると、合計コストは 1+5+5+1=12 となり、これが最小である。