Sightseeing Tour (AOJ 2386)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2386

問題

N頂点の完全無向グラフがある。ハミルトンパス出きるように辺に向きをつけたい。辺の向きを付ける時のコストを与えるのでその様なグラフを作るときの最小コストを求めよ。
1<=N<=100
0<=コスト<=1,000,000

解法

完全グラフのトーナメントグラフは常にハミルトンパスを持つので行列の転置成分の小さい方を取っていけば良い。