一次元上のN点をすべて訪問することを考える。移動を開始してから各点に到達するまでの時間の合計値の最小値を答えよ、という問題。
取り敢えず、ある点と別の一点が指定されれば、その間に通過していない点はないはずなので、現在位置と、一番遠い通過済みの点、というのを状態に持てば良い。追加で必要なのは、今までの合計値と現在の時間。同じ状態があった場合、この後のスコアの最適値は変わらないはずなので、今までの合計値に未到達地点の分だけ現在の時間のゲタをはかせた値が小さい方が、最終的なスコアが良くなるはず。後はただのダイクストラ。
