haraduka https://blog.hatena.ne.jp/haraduka/ haraduka's diary https://haraduka.hatenadiary.jp/ 蟻本 ARC031のD問題解こうと思ったら二部グラフの最大流とか言われてうぇええんって感じなので、グラフについて調べつつ忘れないように書いていきます。最短経路問題には3種類の解法があります。 1. ベルマンフォード法 2. ダイクストラ法 3. ワーシャルフロイド法1.ベルマンフォード法これは単一始点最短路用で、O(V×E)のアルゴリズムであり、負のcostがあっても、負の閉路(重みの総和が負になるような閉路)が存在しなければ使うことができます。スタート地点sからの最短距離を保持するようなd[MAX_V]を用意してあげて、d[s] = 0,それ以外をd[i] = INFとしてあげます。その後、 d[… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fharaduka.hatenadiary.jp%2Fentry%2F2015%2F06%2F22%2F220533" title="最短経路問題 - haraduka&#39;s diary" 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 2015-06-22 22:05:33 最短経路問題 rich https://haraduka.hatenadiary.jp/entry/2015/06/22/220533 1.0 100%