土下座しながら探索中

主に競技プログラミング

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;
}