No.035 D 問題 コード 2つ以上の町で滞在するよりは1つの町で長く滞在した方がお金を稼げる. よって, どの町に行くかを決め, その町への往復の時間を除いて残りの時間をその町の滞在に割り当てた結果稼げる金額が最も大きい町を選ぶ. 行く町への往路の時間はダイクストラ法で求め, 行く町からの復路の時間は道をすべて逆方向の道としたときの町1からの時間なのでこれもダイクストラ法で求める.