fetburner https://blog.hatena.ne.jp/fetburner/ fetburner.core https://fetburner.hatenablog.com/ Coq OCaml AtCoder Beginner Contest の E 問題で2回続けてダイクストラ法が出題される昨今，いかがお過ごしでしょうか？[^1] その2つの E 問題のうち，先に出題された E - Come Back Quickly はいかにも典型的だなあといった問題なので良いのですが，後に出題された E - Train は一筋縄ではいかないものでした．典型的な最短経路問題は辺の長さが定数であるようなグラフを対象としていますが，その問題では辺の長さが，その辺に辿り着くまでの経路長に依存するようなグラフに対してダイクストラ法を適用するのが想定解だったからです． 本記事では，頂点に辿り着くまでの経路長… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ffetburner.hatenablog.com%2Fentry%2F2021%2F02%2F28%2F200020" title="ダイクストラ法の一般化と，その正当性の Coq を用いた検証 - fetburner.core" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-02-28 20:00:20 rich https://fetburner.hatenablog.com/entry/2021/02/28/200020 1.0 100%