ABC208 D Shortest Path Queries 2
0-indexedで考える.
この問題は, 一見シンプルな全頂点対最短経路問題の応用のように見える. しかし, 実はそんなことはなく, 全頂点対最短経路問題の前の部分問題である. 全頂点対最短経路問題を解くアルゴリズムであるワーシャル・フロイド法は, $ dp_{i, j} := 頂点$ iから頂点$ jへの最短経路長 というDPだが, これは$ dp_{k, i, j} := 頂点$ 0~$ kと$ i, jのみを通ったときの頂点$ iから頂点$ jへの最短経路長 というDPの配列を使いまわしたものである.
以上の考察より, この問題を$ dp_{i, j} := 頂点$ iから頂点$ jへの最短経路長 というDPを更新していき それとともに各$ kについて$ dp_{i, j}のその時点での総和を合計したものが答えとなる. 計算量は$ O(N^3)である.