Educational Codeforces Round 38 D問題
競プロ界ではとても有名(?)なダイクストラ法。
典型問題からちょっとひねった問題で個人的には良問だと思った。
codeforces.com
問題文の要約 (訳に脚色入ってます。)
個の町と本の道があって道には通行料が存在。コンサートが全ての町で行われるが、チケット料も町ごとに異なる。町にいる人が、コンサートを一番安く見る時、その料金(他の町へ行くなら通行料往復分込み)を表示せよ。
アルゴリズム
まずグラフ構造に直す。頂点辺、辺の重みは往復分の通行料とできる。
さて、チケット料の情報をどう扱うかが今回最大の工夫ポイント。
まず、一つの頂点 について考える。通常のダイクストラでは最初優先度付きキューに
(0,始点)をpushするが、今回は(チケット料 , )をpushする。
ここで下図のような例を考えて、頂点 からの最短距離の意味を考える。
このように、頂点から頂点までの最短距離が、からへコンサートを見に行った時の最小の料金となっている。後は同様に全ての頂点に対して行えば良いのだが、最小の料金 = 最短距離 に対応しているので最初に(チケット料,)を全ての頂点分pushしてダイクストラ法をやれば 配列 (通常は始点からの距離を格納する配列)に本問題の答えが格納されている。
計算量は、最初にpushする分だけ増えて
(間違ってたらごめんなさい)
ソースコード
#include <bits/stdc++.h> #define REP(i,n) for (long i=0;i<(n);i++) #define FOR(i,a,b) for (long i=(a);i<(b);i++) #define RREP(i,n) for(long i=n;i>=0;i--) #define RFOR(i,a,b) for(long i=(a);i>(b);i--) #define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl; #define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl; #define dump(x) cerr << #x << " => " << (x) << endl; #define CLR(vec) { REP(i,vec.size()) vec[i] = 0; } #define llINF (long long) 9223372036854775807 #define loINF (long) 2147483647 #define shINF (short) 32767 #define SORT(c) sort((c).begin(),(c).end()) #define MIN(vec) *min_element(vec.begin(), vec.end()); #define MAX(vec) *max_element(vec.begin(), vec.end()); using namespace std; typedef long long LL; typedef vector<LL> VL; typedef vector<VI> VVL; typedef pair<LL,LL> pr; struct ver {LL di,node,prev;}; struct Order { bool operator() (ver const& a,ver const& b) const { return a.di > b.di || ((a.di == b.di) && (a.node > b.node)); } }; typedef priority_queue<ver,vector<ver>,Order> pq; // ダイクストラ法 class Dijekstra { private: vector<vector<pr>> E; vector<LL> dist; size_t V; public: Dijekstra() : V(0) { } Dijekstra(size_t v) : V(v),E(v,vector<pr>(0)),dist(v,llINF) {} size_t size() { return V;} void add_edge_directed(LL from,LL to,LL dis){ E[from].push_back(pr(to,dis)); } void add_edge_undirected(LL from,LL to,LL dis){ E[from].push_back(pr(to,dis)); E[to].push_back(pr(from,dis)); } void dijekstra(VI weight){ pq que; REP(i,weight.size()) que.push(ver{weight[i],i,i}); while(! que.empty()){ ver next = que.top(); que.pop(); LL next_v = next.node; if (dist[next_v] < next.di) continue; //決定済み dist[next_v] = next.di; REP(i,E[next_v].size()){ pr e = E[next_v][i]; if (dist[e.first] > next.di+e.second) { que.push(ver{next.di+e.second,e.first,next_v}); } } } } vector<LL> result(void){ return dist; } long result_query(long goal){ return dist[goal]; } }; int main(void){ long n,m,v,u; LL w; cin >> n >> m; Dijekstra dj(n); REP(i,m){ cin >> u >> v >> w; dj.add_edge_undirected(u-1,v-1,w*2); //添え字に注意 } VI weight(n); REP(i,n) cin >> weight[i]; dj.dijekstra(weight); VI ans = dj.result(); REP(i,n) cout << ans[i] << " "; cout << "\n"; return 0; }
注意
数は結構大きくなるのでlong long型じゃないと通らなかった。