TopCoder SRM 675 Div2 Medium ShortestPathWithMagic

幸い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は妥当？