2022-06-23 第二回全国統一プログラミング王決定戦予選の D を解いた
第二回全国統一プログラミング王決定戦予選の D を解いた。
- D - Shortest Path on a Line
https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_d
- 提出: https://atcoder.jp/contests/nikkei2019-2-qual/submissions/32673531
- 解説 AC
- 解けそうで解けない
- 指示通りに辺を張ると数が多すぎて間に合わない
- 戻る必要はほとんどないので L_i で昇順に並べてなんとかしてみたもののうまくいかなかった
- i+1 から i へと長さ 0 の辺を張る
- L_i から R_i へと長さ C_i の辺を張る
- あとはダイクストラ法で求められる
- コスト 0 の辺を張って簡素化するのは何度か見ている気がする
いろいろ届いた。
今日のコミット。