問題 K : 巡回セールスマン問題

2011 年のあの頃，まだプログラミングコンテストはとても平和であり， 我々はルールを精読せずに気軽にコンテストに参加していた． しかし，そこに G○○gle の陰謀は迫っていた． ある日，G○○gle によって秘密裏に買収されていた T○pC○der のコンテストは， 人知れずうちにルールが改変されており，命がけのプログラミングコンテストとなっていた． そして僕は，そこで，何も知らず， まっ先に kita_masa のプログラムのオーバーフローを突いたのだ…．

(iwi)

「うう…ああ…」

wata

「今やるべきことは自分を攻めることではない．チャンスを無駄にする気か？」

…そういえば，今こいつは，部屋に居る全ての人間を一瞬にして倒していた． どうなっているんだ？

wata

「まず，知っているかもしれないが， G○○gle は NP 完全問題を含む多くの計算困難と言われてきた問題に対する多項式時間の効率的なアルゴリズムを持っている．P vs NP 問題を解決したが，敢えてそれを秘匿することによってここまで成長したのだ．」

(iwi)

「もしやとは思っていたが，やはりか…． しかし，お前は今，G○○gle の人間を一瞬にして倒した．もしやお前も…？」

wata

「残念ながら違う．しかし…お前なら，分かるはずだろう？」

…なるほど!! そういうことか． 彼は大学時代，指数時間のアルゴリズムを高速にすることに興味を持っていた． 例え指数時間であっても，指数の底が極めて小さければ， 現実的なインスタンスに対して十分に高速な可能性がある．

wata

「そういうことだ．例えば，今僕は，巡回セールスマン問題の O^*(1.0001ⁿ) 時間のアルゴリズムを完成させようとしている．」

凄まじい，想像以上だ…．

wata

「完成させるにあたって，グラフアルゴリズムに詳しいお前の力が必要だ． 手を貸してくれるな？」

(iwi)

「ああ，勿論だ．まかせろ!!」

5 5
1 2 10
2 3 20
3 4 30
4 5 40
5 1 50

150

5 5
1 5 10
5 4 20
4 3 30
3 2 40
2 1 50

600