AOJ 0616 JOI Park
解法
まず,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; }