JOI 予選 2008 F - 船旅 (AOJ 0526) (2Q, 難易度 5)

実はクエリごとに毎回愚直に Dijkstra 法を回しても間に合う！

• 問題へのリンク

問題概要

最初、辺数 0 本、頂点数 個のグラフが与えられる。頂点番号は である。このグラフに対して 回のクエリが投げられる。

• クエリタイプ 0：2 頂点 が指定されるので、頂点 から頂点 に到達するための最短距離を求める
• クエリタイプ 1：2 頂点 に、重さ の辺（両向）を張る

制約

• 
• 
• 

考えたこと

普通この手のクエリ処理問題では、毎回愚直に求めていては間に合わないことが多い。だが、今回は違う。今回は間に合う。つまり、クエリタイプ 0 が投げられるたびに、

---

• その時点でのグラフに対して、
• 頂点 を始点とした Dijkstra 法などの最短路アルゴリズムを適用する
• 頂点 から頂点 へと至る最短路を求める

---

という方法で間に合うのだ。なお、Dijkstra 法のやり方については、けんちょん本や鉄則本などを参照。

念のために計算量を求めておこう。ここでは、Dijkstra 法としてプライオリティキューを用いない解法を実装するとする。つまり、「まだ使っていない頂点のうち、距離ラベルが最小の頂点を特定し、その頂点に接続している辺についての更新を行う」という方法を実装するとする。このとき、Dijkstra 法の計算量は となる。

よって、全体の計算量は となる。十分間に合う。

コード

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL<<55;

int main() {
    int N, Q;
    cin >> N >> Q;
    
    // グラフを表す隣接行列
    vector G(N, vector(N, INF));

    // 頂点 s を始点としたダイクストラ法
    auto dijkstra = [&](int s) -> vector<long long> {
        vector<long long> dp(N, INF);
        vector<bool> seen(N, false);
        dp[s] = 0;
        for (int iter = 0; iter < N; iter++) {
            // まだ見てない頂点のうち、dp 値が最小の頂点 v を探す
            long long min_dist = INF;
            int min_v = -1;
            for (int v = 0; v < N; v++) {
                if (seen[v]) continue;
                if (dp[v] < min_dist) {
                    min_dist = dp[v];
                    min_v = v;
                }
            }
            if (min_v == -1) break;

            // 頂点 min_v を始点とした緩和を行う
            seen[min_v] = true;
            for (int v = 0; v < N; v++) {
                dp[v] = min(dp[v], dp[min_v] + G[min_v][v]);
            }
        }
        return dp;
    };

    // クエリ処理
    for (int _ = 0; _ < Q; _++) {
        int type, a, b;
        long long w = 0;
        cin >> type >> a >> b;
        --a, --b;
        if (type == 1) {
            // 2 頂点 a, b 間に長さ w の辺が追加される
            cin >> w;
            G[a][b] = min(G[a][b], w);
            G[b][a] = min(G[b][a], w);
        } else {
            // 頂点 a を始点としたダイクストラ法
            const auto &dp = dijkstra(a);

            //for (auto v : dp) cout << v << " "; cout << endl;
            cout << (dp[b] < INF ? dp[b] : -1) << endl;
        }
    }
}