fetburner https://blog.hatena.ne.jp/fetburner/ fetburner.core https://fetburner.hatenablog.com/ OCaml 遥か昔にもOCamlでダイクストラ法を実装したことはあったんですが， 最も近い頂点を線形探索で求めている手抜き実装なので，O(V2)の計算時間を要する（a.k.a. 疎なグラフに対しては遅い）ものでした． 競プロだと入力が疎なグラフに限定されている場面が多々あって[^1]， それを前提に制限時間が決まっているので結構つらいです． 破壊的代入を濫用しているのも気になってましたし，純粋関数型かつ疎なグラフに対して高速な実装を与えます． 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ffetburner.hatenablog.com%2Fentry%2F2018%2F05%2F14%2F022234" title="OCamlでまともなダイクストラ法を実装する - 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 2018-05-14 02:22:34 rich https://fetburner.hatenablog.com/entry/2018/05/14/022234 1.0 100%