[JOI精進録] 難易度7「JOI公園」(第14回日本情報オリンピック 本選C)

問題リンク

atcoder.jp

問題概要

個の広場がある。また、広場同士を結ぶ道路が本ある。
広場1からの最短距離が以下の広場同士が結ばれている道路を削除する。コストを残った道路の距離の総和として、を適切に決めたときのコストの最小値を求めてください。

解説

AC解法 (100/100点)

DIjkstra法を使って広場1からの最短距離をすべて求める。広場1からの道の距離を結ばれている広場の最短距離の大きい方とする。
multisetを使って広場1からの道の距離と道路の距離を管理する。
このとき道路の距離の累積和を取ると、広場1からの道の距離を全探索することでで探索できる。
全体の計算量はとなります。

ACコード

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

int main(){
#define int long long
  int n,m,c,r(numeric_limits<int>::max()); cin >> n >> m >> c;
  // Dijkstraで得たのをsortして逆から累積和すれば勝ち
  vector<tuple<int,int,int>> A(m); vector<vector<pair<int,int>>> G(n);
  for (auto& [a,b,c]:A) (cin >> a >> b >> c),--a,--b,G[a].emplace_back(b,c),G[b].emplace_back(a,c);
  vector<int> dist(n);
  set<pair<int,int>> que; que.emplace(1,0),dist[0]=1;
  while(!que.empty()){
    auto [a,b] = *que.begin(); que.erase(que.begin());
    if (a!=dist[b]) continue;
    for (auto [c,d]:G[b]){
      if (dist[c]&&dist[c]<=dist[b]+d) continue;
      dist[c] = dist[b]+d,que.emplace(dist[c],c);
    }
  }
  multiset<pair<int,int>> ds;
  for (auto& [a,b,c]:A){
    int d = max(dist[a]-1,dist[b]-1);
    ds.emplace(d,c);
  }
  vector<int> dp(m+2); auto rit = ds.rbegin();
  for (int i(0);i < m;++i,++rit){
    dp[m-i]=dp[m-i+1]+rit->second;
  }
  auto it = ds.begin();
  for (int i(0);i < m;++i,++it) r=min(r,c*it->first+dp[i+2]);
  cout << min(r,dp[1]) << endl;
}

提出結果

atcoder.jp