新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

学習記録:ABC #074 D問題

[学習記録] ABC #074 D問題

できなかったD問題を解いてみました。
プログラムはこちら。
atcoder/Main.java at master · ueriku/atcoder · GitHub

コンテストURL

abc074.contest.atcoder.jp

問題

N個の都市があり,ある都市間は道路で双方向に結ばれている。
どの都市からどの都市へも,必要であれば他の都市を経由することで移動ができる。
N*Nの表Aが与えられ,Ai,jは都市iからjへの最短経路の長さを示すものとする。
このような道路の構造が存在するか判定し,存在する場合はそのような道路の構造のうち,存在する道路の長さの和が最小となるものを求めよ。
存在しない場合は-1を出力せよ。

解答

最短距離と聞いて真っ先にワーシャルフロイド法が思い浮かんだが,今回の問題では既に最短距離(と思われるもの)が与えられている。
まずはこのグラフAを更にワーシャルフロイド法に掛けて,本当に最短距離のグラフなのか確かめる。
続いて道路の長さの和を求める必要があるが,解説を見てもなかなか良くわからなかった。
結果的には,各A[i][j]を足し算していき(A[i][j]とA[j][i]は二重カウントしないようにする),
経由地kをとったときに,A[i][j] == A[i][k] + A[k][j]となるようなkが存在する場合,その道路の長さA[i][j]はカウントしないようにすることで,答えを求めることができた。

public void calc() {
    int N = in.nextInt();
    int[][] A = new int[N][N];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            A[i][j] = in.nextInt();
        }
    }

    // グラフAとなる道路の構造が存在しなければtrue
    boolean notExist = false;
    // 答えとなる道路の長さの和(存在しない場合-1)
    long ans = 0;

    // A[i][j]について調べる
    for (int i = 0; i < N; i++) {
        if (notExist) {
            break;
        }
        for (int j = i + 1; j < N; j++) {           
            if (notExist) {
                break;
            }                
            // 道路の長さの和に加える必要がある場合true
            boolean add = true;
            // 各A[i][j]について,経由地kをとった場合を見ていく
            for (int k = 0; k < N; k++) {
                // i == kまたはj == kの場合はカウントしない
                if (i != k && j != k) {
                    // kを経由した際,そちらの方がA[i][j]より短い距離で行けてしまう道が存在する場合,
                    // このグラフAを満たす道路の組み合わせは存在しない                        
                    if (A[i][j] > A[i][k] + A[k][j]) {
                        notExist = true;
                        break;
                    }
                    // kを経由した際の距離がA[i][j]と等しいkが存在する場合,
                    // その距離A[i][j]は答えに加算しない(他の道路の距離を足し合わせることでカウントされるため)
                    else if (A[i][j] == A[i][k] + A[k][j]) {
                        add = false;
                    }
                }
            }
            if (add) {
                ans += A[i][j];
            }
        }   
    }
    // 存在しない場合はansに-1を入れる
    if (notExist) {
        ans = -1;
    }
    out.println(ans);
    out.close();  
}