BoB003-D: Min-Cost Tour

2 secs 1024 MB
kyaneko999's icon kyaneko999

解説

町を辿る順番を 11 つ決めると,各町の間は最短の時間で移動できるような経路を選ぶことが最適です.
各町の間の最短経路は探索順によらないため,予めすべての町のペアに対する最短経路をワーシャルフロイド法などを用いて計算します.
その後,町の探索順を全探索(順列全探索)することによって,旅行にかかる最小の時間を求めることができます.
旅行の最後にはスタート地点の町に戻ってくることに注意してください.

解答例(Python)