CodeIQ過去問集47:復讐
本稿はCodeIQで出題された 第2回プロコン:復讐 という問題を再編集したものです。 ※出題時と記述が一部異なる場合がありますがご了承ください。
第3問:復讐
【ストーリー】
竜宮城から戻った浦島太郎は、乙姫様から賜った玉手箱を開けました。
漁師でありながらも勉強熱心であった浦島太郎は、「絶対開けないで」という言葉は「開けなさい」と同義であることをよくわかっていたからです。
玉手箱を開けると、中から仕留めたはずのいじめっ子たちが武器を構えて現れました。
「…やられる!!」
そう思った瞬間、カメは言いました。
「このサブマシンガンを使うんだ!」
浦島太郎は狙いを定めました。
【問題】
いくつかの狙撃目標地点について、各地点間の移動コストが与えられます。 たとえば次のような4地点について、1→3→2→4または4→2→3→1と移動すると移動コストは7となり、他のどの移動方法よりも低コストになります。
【入力】
標準入力から、1行目に整数値N(4≦N≦9)が与えられます。 2行目以降に、N個の整数値が半角スペースによって区切られたN行のデータ、つまりN×N個の整数値が与えられます。 これはNつの点同士の、移動にかかる時間を行列の形式で表したものです。問題文の例にある4点であれば、
4 0 3 8 2 3 0 4 1 8 4 0 5 2 1 5 0
のようなデータが与えられます。 A→BとB→Aは同じ移動コストですので、左上から右下への対角線(0の部分)に対して必ず対称になっています。
【出力】
標準出力に、最小の移動コスト(整数値のみ)を出力してください。