ひらめの日常

プログラミングと読書と

seg木

AtCoder: 第二回日本最強プログラマー学生選手権-予選- D Shortest Path on a Line (600)

問題はこちら atcoder.jp 個の点がある。その点に対して、以下のように回の操作を行い、辺を追加する。 となる頂点と頂点 の間にコストの辺を追加する。 最終的な頂点からまでの最短距離を求めよ。 以降は0-indexとして話を進める。 解法1 - seg木でdp が与…