TopCoder SRM 551 Div1 Medium ColorfulWolves

問題

有向グラフが与えられる。
0番の頂点から出発して、
枝の出ている頂点のうち、もっとも番号の小さい頂点に移動することを繰り返す。

この移動で、n-1番の頂点にいけるように、
枝を好きに削除することができる。
削除しなければならない枝の本数の最小値を求めよ。

どうやってもn-1番の頂点にいけないとき、-1を出力せよ。

制約条件

n≦50

方針

bitwise2013に全く同一の問題が出ていた。
i番目の頂点にいるとき、j番目に小さい頂点に行きたいなら、
j本の枝を消す必要があるので、コストがjかかる。
これまでに行った頂点には、もう一度行くと無限ループするので行けないようにする必要がある。

この重みつきグラフ上でダイクストラ法をすればよい。

ソースコード

class ColorfulWolves {
	public:
	int getmin(vector <string> colormap) {
		int n = colormap.size();
		bool dp[50] = {};
		vector<vi> e(n);
		
		rep(i, n) rep(j, n) if(colormap[i][j] == 'Y') e[i].pb(j);
		priority_queue<pi> q;
		q.push(mp(0, 0));
		
		while(!q.empty()){
			int c = q.top().second, d = -q.top().first;
			q.pop();
			if(dp[c]) continue;
			dp[c] = 1;
			if(c == n - 1) return d;
			
			rep(i, e[c].size()) q.push(mp(-d - i, e[c][i]));
		}
		return -1;
	}
};