ABC 067 D-Walk and Teleport

D - Walk and Teleport
見た瞬間グラフを作って最小全域木を求めたくなりますが, どの頂点からどの頂点へもテレポートが可能であるため, 辺の数が最悪$10^{10}$以上に膨れることになるため, 最小全域木の構成は辛いです. そのため, 別の解法を考える必要があります.
町は一直線上にあるため, 最小に町を渡ったとき, 徒歩で移動する区間で分割することができます. テレポートで移動したとき, 区間が分割されます. この区間の分割の仕方を考えると, 移動の仕方について, 区間の右端にテレポートして左にいっても, 左端にテレポートして右にいっても同じです(区間の分割の仕方のみによってコストが決定する). よって, 左端から順に, 右に移動するのにテレポートまたは徒歩のコストが低い方で貪欲に移動すればよいことがわかります.
Submission #2919899 - AtCoder Beginner Contest 052