コストの総和を求める
(paizaランク B 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
巡回セールスマン問題 (TSP) とは、辺にコストが付いたグラフが与えられたときに、コストの総和が最小になるようなハミルトン閉路を求める問題です。
有向グラフの各辺のコストを表す隣接行列が与えられます。まずは手始めに、与えられたハミルトン閉路 (v_1, v_2, ..., v_n, v_1) のコストの総和を求めてください。
- 入力される値
-
n
a_{1,1} a_{1,2} ... a_{1,n}
a_{2,1} a_{2,2} ... a_{2,n}
...
a_{n,1} a_{n,2} ... a_{n,n}
v_1 v_2 ... v_n
・ 1 行目に、グラフの頂点数を表す整数 n が与えられます。
・ 続く n 行では、グラフの隣接行列の各要素を表す整数 a_{i,j} が半角スペース区切りで与えられます。(1 ≦ i, j ≦ n) a_{i,j} は、頂点 i から頂点 j への辺のコストを表します。
・ 最後に、ハミルトン閉路を表す頂点の番号を表す整数 v_1, v_2, ..., v_n が半角スペース区切りで与えられます。ただし、閉路に含まれる最後の頂点 v_1 は省略されているので注意してください。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
答えの整数を 1 行で出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 2 ≦ n ≦ 8
・ 0 ≦ a_{i,j} ≦ 100 (1 ≦ i, j ≦ n)
・ a_{i,i} = 0 (1 ≦ i ≦ n)
・ 1 ≦ v_i ≦ n (1 ≦ i ≦ n)
・ v_i ≠ v_j (i ≠ j)
- 入力例1
-
3
0 2 3
3 0 2
2 3 0
1 2 3
- 出力例1
-
6
- 入力例2
-
4
0 42 57 17
96 0 95 25
12 94 0 57
81 35 5 0
2 4 3 1
- 出力例2
-
84
