TopCoder SRM 622 Div1 Easy BuildingRoutes

問題

n頂点からなる有向グラフが与えられる。
このグラフの辺(i, j)であって、二頂点(a, b)を結ぶ最短路の一部となりうるような(a, b)の組がT個以上であるような辺(i, j)の重みw(i, j)の総和を求めよ。

制約条件

n≦50
T≦5000

方針

ワーシャルフロイドして全頂点間最短距離を求めておく。
a, b, i, jを全部まわして、
dist[a][b] = dist[a][i] + w(i, j) + dist[j][b]になっていたら、
cnt(i, j)に1を足す。
cnt(i, j)がT以上であるような辺について重みを全部足せばいい。

ソースコード

class BuildingRoutes {
	public:
	int build(vector <string> dist, int T) {
		
		int d[50][50], cnt[50][50] = {};
		int n = dist.size();
		int ans = 0;
		
		rep(i, n) rep(j, n){
			d[i][j] = dist[i][j] - '0';
		}
		rep(k, n) rep(i, n) rep(j, n) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
		
		rep(a, n) rep(b, n) rep(i, n) rep(j, n){
			
			if(dist[i][j] == '0') continue;
			if(a == b || i == j) continue;
			
			if(d[a][b] == d[a][i] + (int)(dist[i][j] - '0') + d[j][b]) cnt[i][j]++;
		}
		
		rep(i, n) rep(j, n) if(cnt[i][j] >= T) ans += dist[i][j] - '0';
		return ans;
	}
};