AOJ 0616 : JOI Park
問題リンクJOI Park | Aizu Online Judge
問題概要 :
日本語なので略
解法 :
その通りに計算する
愚直にやると遅いので、全ての辺の重みの総和を求め
Xを小さい順に見ていき辺の総和を減らしていく
まず、ノード1からdijkstraで各ノードへの最短距離を求める
その後、各辺について、両端のノードの最短距離のうち大きい方の値と辺の重みとでペアをつくる
そのペアを最短距離を基準にして昇順にソートする
予め辺の総和を求めておく
さきほどのペアを順番に見ていく
ペアの最短距離をXとし、後ろに続く最短距離の値がXである限りその辺を除去していく
値を計算する
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; typedef pair<ll,ll> ll2; const int MAX_V = 100010; const ll LLINF = LLONG_MAX; struct Edge { int src,dst; ll weight; }; struct Data { int cur; ll weight; bool operator < ( const Data &data ) const { if( weight != data.weight ) return weight > data.weight; return cur < data.cur; } }; int V,E; ll C,mindist[MAX_V]; vector<Edge> G[MAX_V],ebuffer; void compute(){ priority_queue<Data> Q; rep(i,V) mindist[i] = LLINF; Q.push((Data){0,0}); mindist[0] = 0; while( !Q.empty() ){ Data data = Q.top(); Q.pop(); rep(i,(int)G[data.cur].size()){ Edge &e = G[data.cur][i]; if( mindist[e.dst] > data.weight + e.weight ) { mindist[e.dst] = data.weight + e.weight; Q.push((Data){e.dst,mindist[e.dst]}); } } } ll edge_sum = 0; vector<ll2> edges; rep(i,E) { Edge &e = ebuffer[i]; edges.push_back(ll2(max(mindist[e.src],mindist[e.dst]),e.weight)); edge_sum += e.weight; } sort(edges.begin(),edges.end()); ll answer = edge_sum; rep(i,(int)edges.size()){ ll X = edges[i].first; while( i < (int)edges.size() && edges[i].first == X ) { edge_sum -= edges[i].second; ++i; } --i; answer = min(answer,C*X+edge_sum); } printf("%lld\n",answer); } int main(){ scanf(" %d %d %lld",&V,&E,&C); rep(i,E){ int A,B; ll D; scanf("%d %d %lld",&A,&B,&D); --A, --B; G[A].push_back((Edge){A,B,D}); G[B].push_back((Edge){B,A,D}); ebuffer.push_back((Edge){A,B,D}); } compute(); return 0; }