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; } };