UTPC2013 L 1円ロード

問題

日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_12）

重みつき有向グラフが与えられる。
各辺には+, -, =の3種類があって、

• +の辺を通ると所持金が1円増える
• -の辺を通ると所持金が1円減る（所持金0のときは通れない）
• =の辺を通ると所持金は変化しない

0円でスタートして0円でゴールする最短距離を求めよ。

制約条件

頂点≦250

方針

kinaba先生の素晴らしい解説スライド参照（http://www.kmonos.net/wlog/sub/utpc13-L.pdf）

0円以上を所持し続けて0円でゴールするルートは、
最初に = を通って、0円→0円のルートを通ってゴールするか、
最初に + を通って0円→0円のルートを通って、最後にちょうど - を通ってゴールするしかない。

この0円→0円の最短距離の表を埋めようとすると、両側から更新しないといけないので、
O(N^4)とかもっとかかりそう。
なので、工夫が必要で、具体的には0円→-1円の最短距離も表にしておけばいい。

それで、ワーシャルフロイド的にやろうとすると解説スライドの原理でNGなので、
距離の短い順にテーブルを確定させていかなければならない。

#define F first
#define S second
 
const int N = 250;
int n;
 
int edge[N][N], dist[N][N];
int dp[2][N][N], inqbest[2][N][N];
 
inline void add(priority_queue<pair<pi, pi> > &q, int t, int a, int b, int d){
	if(dp[t][a][b] <= d) return;
	if(inqbest[t][a][b] <= d) return;
	
	inqbest[t][a][b] = d;
	q.push(mp(mp(-d, t), mp(a, b)));
}
 
int main(){
	
	cin >> n;
	rep(i, n){
		string type;
		cin >> type;
		rep(j, n){
			if(type[j] == 'x') edge[i][j] = inf;
			else if(type[j] == '=') edge[i][j] = 0;
			else edge[i][j] = type[j] == '+' ? 1 : -1;
		}
	}
	rep(i, n) rep(j, n) cin >> dist[i][j];
	
	rep(k, 2) rep(i, n) rep(j, n) dp[k][i][j] = inqbest[k][i][j] = inf;
	
	//dist, type, s, t
	//type = 0なら0円→0円のルート、type = 1なら0円→-1円のルート
	priority_queue<pair<pi, pi> > q;
	rep(i, n) q.push(mp(mp(0, 0), mp(i, i)));
	
	while(!q.empty()){
		int d = -q.top().F.F, t = q.top().F.S;
		int a = q.top().S.F, b = q.top().S.S;
		q.pop();
		
		if(dp[t][a][b] <= d) continue;
		dp[t][a][b] = d;
		if(t == 0 && a == 0 && b == n - 1) break;
		
		//ルートの先頭に1本道を付け足す
		rep(i, n) if(edge[i][a] < inf){
			int nt = t - edge[i][a];
			if(nt < 0 || nt > 1) continue;
			
			add(q, nt, i, b, d + dist[i][a]);
		}
		//ルートの末尾に1本道を付け足す
		rep(i, n) if(edge[b][i] < inf){
			int nt = t - edge[b][i];
			if(nt < 0 || nt > 1) continue;
			if(t == 1 && nt == 0) continue;
			
			add(q, nt, a, i, d + dist[b][i]);
		}
		
		//ルートとルートを合体させる。これがないと通らない。
		//0円→5円→0円→3円→0円みたいに遷移するルートが作れないから。
		//0円→1円のルートも覚えされば不要かも？
		rep(tt, 2 - t){
			rep(i, n){
				add(q, t + tt, a, i, d + dp[tt][b][i]);
				add(q, t + tt, i, b, d + dp[tt][i][a]);
			}
		}
	}
	int ans = dp[0][0][n - 1];
	cout << (ans == inf ? -1 : ans) << endl;
	
	return 0;
}