Shortest Path Queries 2 [AtCoder Beginner Contest 208 D]

https://atcoder.jp/contests/abc208/tasks/abc208_d

前提知識

• （ワーシャルフロイド）

解説

https://atcoder.jp/contests/abc208/submissions/23994717

ワーシャルフロイドを正確に理解していれば解ける問題。
いや、この問題を理解することがワーシャルフロイドを正確に理解することを助けるのかもしれない。
ワーシャルフロイドの知識がない前提で説明を試みる。
前半はほぼフィクションです。

何から手を付けようか

クエリ問題への取り組み方の1つとして差分計算だけすることで高速化するという方針がある。
状況を整理してみると、kの値が増えることで使える遷移が増えて、差分的な要素が出てくる。
なので、kの値を1から増やしていくことで差分計算ができないかということを考える。

初期状態

初期状態を考えよう。
今回はk=0から始めてみよう。
（k=1からじゃないの？という突っ込みはちょっと置いておいて…）
これで一旦f(s,t,0)を考えてみると、使えるのはs->tへの直接の遷移だけとなる。
これを頭において、二次元配列にマッピングしてみる。

dist[s][t] := sからtへ移る場合の最短距離

これを定義すると、k=0の場合は、

dist[i][i] = 0 （同じ場所の場合は0）
dist[A][B] = C （直接遷移がある場合）
dist[other][other] = inf （遷移が無い場合は∞）

到達できない場合は他の最短距離でも良くやっているようなinfにしておく。
これが初期状態となる。

差分計算

この状態からk=1を考えてみよう。
これは遷移の経由点として1が使えるようになっていることになる。
端的にはs->1->tができるようになったことになる。
なので、1を経由したパターンだけを見て最短経路の更新をしていこう。
つまり、

dist[s][t] = min(dist[s][t], dist[s][1] + dist[1][t])

で更新していくことになる。
こうすると1を経由する遷移をすべて反映させたdist配列が用意される。
こうやって更新すると、f(s,t,1) = dist[s][t]となっている。
なので、これを答えに足し合わせていこう。

更にもう一歩差分計算

同様にもう一歩計算してみよう。

dist[s][t] = min(dist[s][t], dist[s][2] + dist[2][t])

これをやると、dist[s][2]の間は1が考慮された最短経路になっているし、dist[2][t]の間も同様に1が考慮された最短経路になっている。
なのでdist[s][t]は2以下が考慮された最短経路になっている。
よって、この差分計算を進めていくとkがインクリメントされていって、上手く計算ができる。

で、これをやっているアルゴリズムがワーシャルフロイドになる。

計算量

実際に実装してみて眺めてみるとはっきり理解ができると思うが、差分計算をk=1～NまでN回行うのでO(N)、
差分計算自体の計算量はsとtの列挙をやるのでO(N²)
よって全体O(N³)となり、間に合う。

int N, M;
int dist[401][401];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;

    rep(i, 0, N) rep(j, 0, N) dist[i][j] = inf;
    rep(i, 0, N) dist[i][i] = 0;

    rep(i, 0, M) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        dist[a][b] = c;
    }

    ll ans = 0;
    rep(k, 0, N) {
        rep(i, 0, N) rep(j, 0, N) chmin(dist[i][j], dist[i][k] + dist[k][j]);
        rep(i, 0, N) rep(j, 0, N) if (dist[i][j] < inf) ans += dist[i][j];
    }
    cout << ans << endl;
}