TopCoder SRM 652 Div1 Medium MaliciousPath

本番近いところまでは行けたが、状態遷移が混乱して解答には至れず。
http://community.topcoder.com/stat?c=problem_statement&pm=13596

問題

N頂点M有向辺からなるグラフがある。
各辺にはコストが付与されている。

ここで0番の頂点から(N-1)番の頂点に移動したい。
Aliceは0番から(N-1)番の頂点に最小コストで移動したい。
一方BobはAliceの行動を邪魔し、0番から(N-1)番の頂点に至るコストをできるだけ大きくしたい。

Aliceが各頂点から移動する辺を選ぶ際、最大K回まで邪魔をして別のBobが選んだ辺を通して移動させることができる。
AliceはBobの残り邪魔回数を知っている。

互いに最適手を取ったとき、Aliceの総移動コストはいくらか。

解法

Aliceは特にBobの邪魔回数を気にせず、とにかくゴールの最短路を選べばよい。
一方BobはAliceの経路より(邪魔回数を１回消費しても)別経路を選ばせた方がコストが高くなる場合、Aliceをそちらに誘導する。

この前提を踏まえ、dp[残り邪魔回数][現在の頂点]=ゴールまでのコスト、を最小化するようDPを行う。
まず残り邪魔回数が0回の時は、単に(N-1)番の頂点から逆辺をダイクストラでたどればゴールまでの最短コストが求められる。

残り邪魔回数がi回(i＞0)の時を考える。
現在の頂点をxとし、xからつながる各辺をe(行先y,コストc)とすると、Bobは邪魔をすることでdp[i][x]=max(dp[i-1][e.t] + e.c)に誘導することができる。
よって残り邪魔回数(i-1)回の処理を終えた後、m[x]=max(dp[i-1][e.t] + e.c)となる値を考える。

後はdp[i][x]を順に逆辺reを辿るダイクストラで求める場合、コストをdp[i][re.to]=max(m[re.to], dp[i-1][x]+re.c)で更新しながらダイクストラを行えばよい。
コストがm[re.to]未満にならない(未満になりそうなら、Bobは邪魔回数を消費してm[re.to]かかる辺に誘導する)点がコツ。

ll dp[1010][1010];
ll ma[1010];
class MaliciousPath {
	public:
	vector<pair<int,int> > E[1010],RE[1010];
	long long minPath(int N, int K, vector <int> from, vector <int> to, vector <int> c) {
		int i,x,y;
		
		FOR(i,N) E[i].clear(),RE[i].clear();
		FOR(i,from.size()) E[from[i]].push_back(make_pair(c[i],to[i]));
		FOR(i,from.size()) RE[to[i]].push_back(make_pair(c[i],from[i]));
		ZERO(dp);
		ZERO(ma);
		
		for(i=0;i<=K;i++) {
			
			FOR(x,N-1) {
				dp[i][x]=1LL<<50;
				if(i==0) ma[x]=-1LL<<50;
				else FOR(y,E[x].size()) ma[x]=max(ma[x], dp[i-1][E[x][y].second]+E[x][y].first);
			}
			
			priority_queue<pair<ll,int> > Q;
			FOR(x,N) Q.push(make_pair(-dp[i][x],x));
			while(Q.size()) {
				pair<ll,int> p=Q.top();
				int cur=p.second;
				ll co=dp[i][cur];
				Q.pop();
				if(co!=-p.first) continue;
				
				FOR(x,RE[cur].size()) {
					int tar=RE[cur][x].second;
					ll co2=max(ma[tar],co+RE[cur][x].first);
					if(co2<dp[i][tar]) {
						dp[i][tar]=co2;
						Q.push(make_pair(-dp[i][tar],tar));
					}
				}
			}
		}
		
		if(dp[K][0]>=1LL<<50) return -1;
		return dp[K][0];
		
	}
}

まとめ

邪魔回数(i-1)回の状態を用いて何度もダイクストラをする、という点は思いつけたけど、状態遷移がうまく書けず時間内に解ききれなかった。