TopCoder SRM 551 Div1 Medium ColorfulWolves

SRMで初めて本番解けたDiv1 Medium。
ただ、当時30行ぐらい書いたのに今解きなおしたら10行で済んだ。
http://community.topcoder.com/stat?c=problem_statement&pm=12142

問題

N頂点からなる有向辺グラフがある。
各頂点では、1回移動するとそこから移動可能な頂点のうち、最も小さな番号の頂点に遷移する。

幾つかの辺を削除し、0番の頂点から(N-1)番の頂点に移動できるようにしたい。
削除すべき最小の変数を答えよ。

解法

a→bに至る辺がある場合、その辺を通るにはc

int N,mat[51][51];
class ColorfulWolves {
	public:
	int getmin(vector <string> colormap) {
		int x,y,t;
		N=colormap.size();
		FOR(x,N) {
			t=0;
			FOR(y,N) mat[x][y]=colormap[x][y]=='Y'?t++:99999;
			mat[x][x]=0;
		}
		FOR(t,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][t]+mat[t][y]);
		if(mat[0][N-1]>=99999) return -1;
		return mat[0][N-1];
	}
}

まとめ

本番も一応解けていたとはいえだいぶ冗長なコード。
成長したもんだね。