Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題 "Single Source Shortest Path"
https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_A
・単一始点最短経路
僕が作成、提出したコードは、以下のとおりです。
Aizu Online Judge in C++ #GRL_1_A : Single Source Shortest Path
/* Aizu Online Judge in C++ #GRL_1_A : Single Source Shortest Path https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_A 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; const ll inf=9999999999999999; int main(void){ ll vv,ee,r; cin>>vv>>ee>>r; vector<ll> d(vv,inf); vector<vector<pair<ll,ll>>> e(vv); for(ll i=0;i<ee;i++){ ll s,t,d; cin>>s>>t>>d; e[s].push_back({d,t}); } priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> q; d[r]=0; for(auto i : e[r]){ q.push(i); } while(!q.empty()){ auto num=q.top(); q.pop(); if(d[num.second]<num.first){ continue; } d[num.second]=num.first; for(auto j : e[num.second]){ q.push({j.first+num.first,j.second}); } } for(auto i : d){ if(i==inf){ cout<<"INF"<<endl; }else{ cout<<i<<endl; } } return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/