2010年 日本情報オリンピック春合宿OJから、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#finals - 本選会場 (Finals)
https://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day3_22.pdf
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #finals - 本選会場 (Finals) https://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day3_22.pdf 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; using P=pair<ll,ll>; using Graph=vector<vector<P>>; ll n,m,k,ans=0; Graph g; vector<bool> used; vector<ll> s; int main(void){ cin>>n>>m>>k; g.resize(n); for(ll i=0;i<m;i++){ ll a,b,c; cin>>a>>b>>c; a--; b--; g[a].push_back(make_pair(c,b)); g[b].push_back(make_pair(c,a)); } priority_queue<P,vector<P>,greater<P>> pq; used.assign(n,false); pq.emplace(0,0); while(!(pq.empty())){ ll price,to; tie(price,to)=pq.top(); pq.pop(); if(used[to]){ continue; } used[to]=true; ans+=price; s.emplace_back(price); for(auto i : g[to]){ pq.push(i); } } sort(s.rbegin(),s.rend()); for(ll i=0;i<k-1;i++){ ans-=s[i]; } cout<<ans<<endl; return 0; }