TopCoder SRM 622 Div1 Easy BuildingRoutes

SRM622は午前回だったので不参加。
練習ではDiv1Easyで長時間かかり、Div1 Medium/Div2 Medium/Div2 Hardがどれも凡ミス連発してたので結果的に出なくてよかったかも…。
http://community.topcoder.com/stat?c=problem_statement&pm=13193

問題

N個の都市があり、各都市間の道路の長さR[x][y]が与えられる。

各都市から各都市に向け、計(N-1)*N個のバスが運行している。
各バスは目的地に向けた最短路のうちいずれかを通る。
各道路のうち、T個以上のバスが通る可能性があるものを求め、その長さの総和を求めよ。

解法

まずWarshall-Floydで都市X,Y間の距離D[X][Y]を求める。
次に、X->Yに運行するバスがa->bの道路を通る可能性があるのは、X->a->b->YのパスがX->Yの最短路の１つである場合である。
よって、D[X][a]+R[a][b]+D[b][Y]==D[X][Y]ならR[a][b]を走るバスが1個増える。

バスの始点・終点X,Yに対し道路の両端a,bを総当たりで処理すると、O(N^4)で各道路を通る可能性のあるバスの数を求められる。

class BuildingRoutes {
	int mat[51][51];
	int num[51][51];
	public:
	int build(vector <string> dist, int T) {
		int N=dist.size();
		int i,x,y,x2,y2;
		FOR(x,N) FOR(y,N) mat[x][y]=dist[x][y]-'0';
		FOR(i,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][i]+mat[i][y]);
		int ret=0;
		FOR(x,N) FOR(y,N) if(x!=y) {
			i=0;
			FOR(x2,N) FOR(y2,N) if(x2!=y2 && mat[x2][x]+dist[x][y]-'0'+mat[y][y2]==mat[x2][y2]) i++;
			if(i>=T) ret+=dist[x][y]-'0';
		}
		return ret;
	}
}

まとめ

問題文を見間違えて「最低T個以上通る～～」と勘違いし、O(N^5)かかるんじゃ…と迷って大幅タイムロスした。