AOJ 0616 JOI Park

問題文

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

解法

まず，0を始点としてダイクストラで，各点への最短路重みを求めておく．
そして，その重みで頂点をソートしておく．また，あらかじめ辺全体の重みの総和を求めておく．
Xの候補としては，各頂点への最短路重みだけ考えればよいことは明らかにわかる．
つまり，Xの候補はN通り．
ここでXを大きくしていき，その各過程で点0から到達可能な頂点集合Sについて，今追加しようとしている頂点からSと接続している辺の重みを，総和から減らしていくと良い．
こうしていった中で一番小さい値が求める答えである．

計算量は O(ElogV + VlogV)

ソースコード

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

using ll = long long;
using P = pair<ll, ll>;

struct edge {
    int from, to;
    ll weight;
};

using edges = vector<edge>;
using graph = vector<edges>;

constexpr ll INF = 1e18;

int main() {
    ll N, M, C;
    cin >> N >> M >> C;

    graph g(N);
    ll sum_cost = 0;
    for(int i=0; i<M; ++i) {
        int a, b;
        ll d;
        cin >> a >> b >> d;
        a--; b--;
        g[a].push_back((edge){a, b, d});
        g[b].push_back((edge){b, a, d});
        sum_cost += d;
    }

    vector<P> d(N);
    for(int i=1; i<N; ++i) {
        d[i] = make_pair(INF, i);
    }
    d[0] = make_pair(0, 0);
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(make_pair(0, 0));
    while(!que.empty()) {
        P p = que.top();
        int v = p.second;
        que.pop();
        if(d[v].first > p.first) {
            continue;
        }
        for(auto& e : g[v]) {
            if(d[e.to].first > d[v].first + e.weight) {
                d[e.to].first = d[v].first + e.weight;
                que.push(make_pair(d[e.to].first, e.to));
            }
        }
    }
    sort(d.begin(), d.end());
    ll res = 1e18;
    set<int> S;
    for(int i=0; i<N; ++i) {
        for(auto& e : g[d[i].second]) {
            if(S.count(e.to) == 1) {
                sum_cost -= e.weight;
            }
        }
        res = min(res, sum_cost + C * d[i].first);
        S.insert(d[i].second);
    }
    cout << res << endl;
}