第13回日本情報オリンピック 予選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#E - タクシー (Taxis)
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #E - タクシー (Taxis) https://atcoder.jp/contests/joi2014yo/tasks/joi2014yo_e 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; using P=pair<ll,ll>; bool tf_min(ll& n,ll m){ if(n>m){ n=m; return true; }else{ return false; } } int main(void){ ll n,k; cin>>n>>k; vector<ll> c(n),r(n); for(ll i=0;i<n;i++){ cin>>c[i]>>r[i]; } vector<vector<ll>> g(n); for(ll i=0;i<k;i++){ ll a,b; cin>>a>>b; g[--a].push_back(--b); g[b].push_back(a); } priority_queue<P,vector<P>,greater<P>> pq; pq.push({0,0}); vector<ll> v(n,1e9); v[0]=0; while(!(pq.empty())){ auto[i,j]=pq.top(); pq.pop(); if(v[j]<i){ continue; } queue<ll> q; q.push(j); vector<ll> v2(n,-1); v2[j]=0; while(!(q.empty())){ ll t=q.front(); q.pop(); if(v2[t]==r[j]){ continue; } for(ll to : g[t]){ if(v2[to]==-1){ v2[to]=v2[t]+1; q.push(to); if(tf_min(v[to],i+c[j])){ pq.push({v[to],to}); } } } } } cout<<v[n-1]<<endl; return 0; }