読者です 読者をやめる 読者になる 読者になる

AOJ 0526 Boat Travel

解法

基本はワーシャルフロイドだが,それだと間に合わないので工夫する.
仮に島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);
                    }
                }
            }
        }
    }
}