幸い2問+1ChalでHighest更新しました。
https://community.topcoder.com/stat?c=problem_statement&pm=14091
問題
N頂点のグラフにおいて、2点間の移動時間が与えられる。
ただ、この移動においてK回まで本来の半分の時間で移動できる(1回の移動で複数回半減させることはできない)。
0番から1番の頂点に至る最短時間を求めよ。
解法
状態として、(現在位置,残り半減回数)の2値を使って、あとはDijkstraを使うだけ。
int cost[51][51]; class ShortestPathWithMagic { public: double getTime(vector <string> S, int k) { int i,j,x,y; int N=S.size(); FOR(x,N+1) FOR(y,k+1) cost[x][y]=999999; cost[0][k]=0; priority_queue<pair<int,int> > PQ; PQ.push({0,k*100}); while(PQ.size()) { auto r=PQ.top(); PQ.pop(); int co=-r.first; int nk=r.second/100; int cur=r.second%100; if(cur==1) return co/2.0; if(cost[cur][nk]<co) continue; FOR(i,N) { if(cost[i][nk]>cost[cur][nk]+2*(S[i][cur]-'0')) { cost[i][nk] = cost[cur][nk]+2*(S[i][cur]-'0'); PQ.push({-cost[i][nk], nk*100+i}); } if(nk && cost[i][nk-1]>cost[cur][nk]+(S[i][cur]-'0')) { cost[i][nk-1] = cost[cur][nk]+(S[i][cur]-'0'); PQ.push({-cost[i][nk-1], (nk-1)*100+i}); } } } return 0; } }
まとめ
やることは単純だけど、Dijkstraをさらっと書けないとめんどいのでDiv2 500ptは妥当?