ARC035 C - アットコーダー王国の交通事情

問題文

http://arc035.contest.atcoder.jp/tasks/arc035_c

解法

頂点数が小さいので，ワーシャルフロイドでよい．
ただし，建設するたびにワーシャルフロイドすると間に合わない．

よく考えると，x-y 間に橋を作ったときに最短経路が変わるのは，x-yを経由するという意味にほかならない．
すると，最短経路を更新するときは
d[i][j] = min(d[i][j], d[i][x] + d[x][y] + d[y][j])
のように，i -> x -> y -> j という経路だけ確認すれば良いことになる．
もちろん，i -> y -> x -> j の経路も確認する．
これは O(N^2) でできるので，クエリに対して O(KN^2) で求まる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr int INF = 1e9;

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> d(N, vector<int>(N, INF));
    for(int i = 0; i < N; ++i) {
        d[i][i] = 0;
    }
    for(int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        d[a][b] = min(d[a][b], c);
        d[b][a] = d[a][b];
    }

    for(int k = 0; k < N; ++k) {
        for(int i = 0; i < N; ++i) {
            for(int j = 0; j < N; ++j) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    int K;
    cin >> K;
    while(K--) {
        int x, y, z;
        cin >> x >> y >> z;
        x--;
        y--;
        if(d[x][y] > z) {
            d[x][y] = d[y][x] = z;
            for(int i = 0; i < N; ++i) {
                for(int j = i + 1; j < N; ++j) {
                    int t = d[i][x] + d[x][y] + d[y][j];
                    t = min(t, d[i][y] + d[y][x] + d[x][j]);
                    d[i][j] = d[j][i] = min(d[i][j], t);
                }
            }
        }
        ll sum = 0;
        for(int i = 0; i < N; ++i) {
            for(int j = i + 1; j < N; ++j) {
                sum += d[i][j];
            }
        }
        cout << sum << endl;
    }
}

感想

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0526
これと一緒．AOJのほうは制約がちょっと違うからゴリ押せるんだけど．