AOJ 1457 Omnes Viae Yokohamam Ducunt? (ICPC アジア 2024 C)

面白かった！　一見 MST の問題に見えるけど、主客転倒すると Dijkstra だった。

• 問題へのリンク（仮）

問題概要

頂点数 、辺数 の連結な単純無向グラフが与えられる。頂点 には重み がついていて、辺 には重み がついている。このグラフの全域木のコストを次のように定めるとき、最小コストを求めよ。

【全域木のコスト】
全域木の各辺 に対して、辺 を削除したとき、頂点 1 から到達できなくなる頂点 についての の総和を とする。このとき、全域木のコストは

で与えられる。

制約

• 
• 

考えたこと

全域木のコストがとても複雑なので、具体例で考えてみることにした。たとえば下の木を考えてみる。頂点番号は 1, 2, 3, 4, 5, 6 として、辺番号は 1, 2, 3, 4, 5 とする。このとき、コストは

• 辺 1：
• 辺 2：
• 辺 3：
• 辺 4：
• 辺 5：

の総和となる。

この総和を ごとに整理しなおすと、

• 頂点 2：
• 頂点 3：
• 頂点 4：
• 頂点 5：
• 頂点 6：

となる。こうしてみると、各頂点 に対して、

となっていることに気づく。つまり、求めるコストは次のように書き直せるのだ！！！

---

---

ここで、頂点 1 から頂点 までの最短距離を とすると、おそらく答えは

になるのではないかと予想できる。これを示すには、ある全域木が存在して、その全域木上で頂点 1 から頂点 までの距離が であることが言えればよい。

そして、そのような全域木として、実際に「頂点 1 を始点とする Dijkstra 木」がある。

以上より、求める最小コストは上記の式となることが言えた。priority queue を用いる普通の Dijkstra 法を実装したとき、計算量は と評価できる。

コード

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

int main() {
    using Edge = pair<int, long long>;
    using Graph = vector<vector<Edge>>;

    int N, M, u, v;
    long long q;
    cin >> N >> M;
    vector<long long> p(N);
    for (int i = 0; i < N; i++) cin >> p[i];
    Graph G(N);
    for (int i = 0; i < M; i++) {
        cin >> u >> v >> q, u--, v--;
        G[u].emplace_back(v, q);
        G[v].emplace_back(u, q);
    }

    vector<long long> dp(N, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> que;
    dp[0] = 0;
    que.push({0, 0});
    while (!que.empty()) {
        auto [cur, v] = que.top();
        que.pop();
        if (cur > dp[v]) continue;
        for (auto e : G[v]) {
            if (dp[v] + e.second < dp[e.first]) {
                dp[e.first] = dp[v] + e.second;
                que.push({dp[e.first], e.first});
            }
        }
    }
    long long res = 0;
    for (int v = 0; v < N; v++) {
        res += dp[v] * p[v];
    }
    cout << res << endl;
}