AOJ 0526 Boat Travel

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0526

解法

基本はワーシャルフロイドだが，それだと間に合わないので工夫する．
仮に島a, b間の船舶が更新された時，グラフ上の異なる2つの島u, vの最短経路は，

• u -> a -> b -> v つまり d[u][a] + d[b][v] + d[a][b]
• u -> b -> a -> v つまり d[u][b] + d[a][v] + d[a][b]
• そもそも a, b 間の船舶を利用しない，つまり d[u][v]

の3通りで，これらの中から最小のものを d[u][v] に入れれば良い．

これだと計算量は，各更新に対して O(N^2) で，更新は高々 10^3 回なので間に合う．

まぁ，毎回ダイクストラしてもいいけど．それだと高々 2.5 * 10^7 ぐらいか．

ソースコード

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

constexpr int INF = 1e9;

int main() {
    int n, k;
    while(cin >> n >> k, n) {
        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<k; ++i) {
            int a;
            cin >> a;
            if(a == 0) {
                int b, c;
                cin >> b >> c;
                b--; c--;
                cout << (d[b][c] == INF ? -1 : d[b][c]) << endl;
            } else {
                int b, c, e;
                cin >> b >> c >> e;
                b--; c--;
                if(d[b][c] <= e) {
                    continue;
                }
                for(int j=0; j<n; ++j) {
                    for(int l=0; l<n; ++l) {
                        d[j][l] = min(d[j][l], min(d[j][b] + d[c][l], d[j][c] + d[b][l]) + e);
                    }
                }
            }
        }
    }
}