WARush

SRMの結果とか、解けた問題のコードを書いていきます

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