SRM622 Div1 Easy "BuildingRoutes"
問題
TopCoder Statistics - Problem Statement
訳
Nlogonia共和国にはN個の都市がある。簡便のため、これらの都市には0~N-1の番号を付ける。2つの任意の都市i, jには、iからjに向かう一方通行の道路がある。あなたはN個の文字で構成される文字列をN個持つ、String配列のdistが与えられる。dist[i][j]はiからjへの道路の長さを表している。
道路の長さは1から9までであり、それは'1'から'9'までの文字で表されている。iとjが違う値だとして、dist[i][j]は'1'から'9'のどれかである。dist[i][i]は'0'である。dist[i][j]とdist[j][i]は違う可能性もあることに注意して欲しい。
毎年、アルゴリズム記念日(Nlogonia共和国において、最も重要な記念日)では、人々は都市間で旅行をする。より正確には、i, jの全てのとりうるペアにおいて、バスが人々を乗せてiからjへと向かう。バスの運転手は、現在位置から目的の場所まで最短距離のルートを通るように運転する。もし最短距離のルートが複数あれば、バスの運転手はそれらを任意に選ぶ。
Nlogoniaにある道路には制限がある。あなたは次のような意味の整数Tが与えられる。
それぞれの道路において、バスの通る回数がTより少ない場合、安全であるとする。 そうでない場合、つまりT以上バスが通る可能性がある場合、安全でないとする。
政府は次のアルゴリズム記念日がくる前に、安全でない道路を再建することにした。安全でない道路の長さの合計を返せ。
制約
2 <= N <= 50
1 <= T <= 2500
考えたこと
全都市間の最短距離をワーシャルフロイドで調べるついでに、どのような経路を辿ったのか記録しておく。それが終わったら、記録した経路から各道路を使った回数を出し、T以上の道路の長さを足していけばいい。余裕
↓
Faild System Test
↓
あ、最短パスが複数あった場合考えてなかった。テヘ
解法
ワーシャルフロイドで全都市間の最短距離を出すとこまではよい。
都市i, j間の最短ルートをD(i, j)、都市i, j間の直通道路の長さをL(i, j)とする。
都市xからyへの最短ルートにおいて、都市aからbへと繋ぐ道路を使用する可能性があるかどうかは、D(x, y) == D(x, a) + L(a, b) + D(b, y)であるかどうか、ということがいえる。(うーん。。なるほど。。)可能性があれば、a -> bの使用回数をインクリメントしていけばよい。
計算量はO(N^4)
ソースコード
int N; int L[55][55], D[55][55], C[55][55]; class BuildingRoutes { public: int build(vector <string> dist, int T) { N = dist.size(); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { L[i][j] = D[i][j] = dist[i][j] - '0'; } } // ワーシャルフロイド for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { for (int k = 0; k < N; k++) { if (D[j][i] + D[i][k] < D[j][k]) { D[j][k] = D[j][i] + D[i][k]; } } } } // 道路の使用回数 memset(C, 0, sizeof(C)); for (int x = 0; x < N; x++) { for (int y = 0; y < N; y++) { for (int a = 0; a < N; a++) { for (int b = 0; b < N; b++) { if (D[x][y] == D[x][a] + L[a][b] + D[b][y]) C[a][b]++; } } } } int res = 0; for (int a = 0; a < N; a++) { for (int b = 0; b < N; b++) { if (C[a][b] >= T) res += L[a][b]; } } return res; } };