去年のPCK予選第9問目。前回は強引に偽ダイクストラ的なことをして解いたが、今回はベルマンフォードを用いた正攻法で解いた。(※正の辺だけでやって、負辺分を後で引く拡張ダイクストラでも通った。)
今までベルマンフォード解いたことなかったんだけど、蟻本読んで理解して、実装したくなったので。
計算量的には隣接行列の無いワーシャルフロイドだなーって感じ。仕組みは違うけど。
SpaghettiSourceの
>これは動的計画法に基づくアルゴリズムで，k 回目の更新によって始点から k ステップ以下で進む場合の最短距離が計算される．もし n 回目にもまだ更新があるのならば，経路はどこかに負の閉路を含んでいるので，その頂点への経路には負閉路が存在するとして距離を負の無限大に設定する．
という説明が分かりやすいです。まあ頂点数-1回以内にたどり着けるのは考えてみたら明らかですからね。
O( (頂点の数)*(辺の数) )とそれなりに早い。
とりあえずケーキ屋とか普通のノードとか一つにまとめるために色々キモいことをしているが集中すればバグは起こらないし、こちらの方が絶対コーディング時間は減るのでオススメ。
イメージ的には、
「頂点を2^(ケーキ屋の数)個複製して、辺も同じ数複製する。(ただしケーキ屋の前を二度と通らないという制約は考慮する。)」
そんな感じ。
#include <iostream> #include <vector> #include <cstdlib> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define INF (1<<21) struct EDGE{ int from,to,cost; EDGE(int a,int b,int c){from = a , to = b , cost = c;} }; int m,n,K,d; int get(string s){ if(s[0] == 'H')return n+m; if(s[0] == 'D')return n+m+1; if(s[0] == 'L')return m+atoi(s.substr(1).c_str())-1; if(s[0] == 'C')return atoi(s.substr(1).c_str())-1; } int main(){ while(cin >> m >> n >> K >> d , m ){ // Input vector<int> cake(m); rep(i,m)cin >> cake[i]; vector<EDGE> E; rep(i,d){ string a,b; int c; cin >> a >> b >> c; E.push_back(EDGE(get(a),get(b),c*K)); E.push_back(EDGE(get(b),get(a),c*K)); } // Init int d[1<<6][100+6+2]; rep(i,1<<6)rep(j,100+6+2) d[i][j] = INF; d[0][n+m] = 0; // Bell-man Ford while(true){ bool update = false; rep(i,E.size()){ EDGE e = E[i]; rep(bit,1<<m){ if( e.to < m && (bit & (1<<e.to)) ) continue; if( e.to < m ){ if( d[bit|(1<<e.to)][e.to] > d[bit][e.from] + e.cost - cake[e.to]){ d[bit|(1<<e.to)][e.to] = d[bit][e.from] + e.cost - cake[e.to]; update = true; } }else{ if( d[bit][e.to] > d[bit][e.from] + e.cost){ d[bit][e.to] = d[bit][e.from] + e.cost; update = true; } } } } if(!update)break; } //Output int ans = INF; rep(i,1<<m) ans = min(ans,d[i][n+m+1]); cout << ans << endl; } }
