WARush

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

SRM626 Div1 "NegativeGraphDiv1"

問題

TopCoder Statistics - Problem Statement

ナンシーはN個のノードとE個のエッジを持つ有向グラフを持っていた。ノードには1からNまでの番号が振られている。それぞれのエッジには正の整数の重みが設定されている。このグラフは3つのint配列 from, to, weightにて表現される。グラフはfrom[i]からto[i]に向かうエッジを持ち、その重みはweight[i]である。グラフには開始ノードと終了ノードが同じエッジを、複数個持つ可能性がある。また、開始ノードと終了ノードが同じエッジを持つ可能性がある。

ナンシーは現在ノード1にいる。彼女はエッジを辿って他のノードに移動することができる。その移動コストはエッジの重みである。ナンシーの目的は、頂点Nへ移動し、その時かかるコストの合計を最小にすることである。

ナンシーには移動コストを抑えるための特別なパワーがある。彼女がエッジを移動するたびに、彼女はその特別なパワーを使い一時的にエッジの重みを負の数とすることができる。あなたはこのパワーの使用回数であるint chargesが与えられる。このパワーの効果は、エッジの移動が終わると切れてしまう。ナンシーはパワーを好きなときに使うことができる。エッジを移動するたびにパワーを使うか、後々のため使わないかを選ぶことができる。

ナンシーの旅にかかる最小コストを返せ。

制約

1 <= N <= 50
1 <= E <= 2500
1 <= weight[i] <= 10^6
1 <= charges <= 10^9

解法

TopCoder SRM 626 Div1 Medium NegativeGraphDiv1、Div2 Hard NegativeGraphDiv2 - kmjp's blog
こちらを参考にしました。m(_ _)m

まさかのワーシャルフロイドと累乗行列(ダブリング)のコラボ
かっけぇ・・・



ソースコード

/*
G[i][j] :=
iからjへ向かうエッジの最大重み
存在しなければ場合は-1
*/
long long G[55][55];

/*
S[i][j] :=
iからjへ向かうときの最小コスト
S2は一時保存用
*/
long long S[55][55], S2[55][55];

/*
D[i][j] :=
特別なパワーを2^n回使ったときのiからjへ向かうときの最小コスト
D2は一時保存用
*/
long long D[55][55], D2[55][55];

class NegativeGraphDiv1 {
public:

    long long findMin(int N, vector <int> from, vector <int> to, vector <int> weight, int charges) {
        // 1~N ⇒ 0~N-1
        for (int i = 0; i < from.size(); i++) {
            from[i]--;
            to[i]--;
        }

        // G, S, D初期化
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                G[i][j] = -1;
                S[i][j] = S2[i][j] = i == j ? 0 : INF;
                D[i][j] = D2[i][j] = i == j ? 0 : INF;
            }
        }
        for (int i = 0; i < from.size(); i++) {
            G[from[i]][to[i]] = max(G[from[i]][to[i]], (long long)weight[i]);
            S[from[i]][to[i]] = min(S[from[i]][to[i]], (long long)weight[i]);
        }
        //- ワーシャルフロイドで、パワーを1回も使わない状態の最小コストを算出
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    S[j][k] = min(S[j][k], S[j][i] + S[i][k]);
                }
            }
        }
        //- 2^0回(=1回)パワーを使ったときの最小コストを算出
        for (int a = 0; a < N; a++) {
            for (int b = 0; b < N; b++) {
                for (int x = 0; x < N; x++) {
                    for (int y = 0; y < N; y++) {
                        if (G[x][y] == -1) continue;
                        D[a][b] = min(D[a][b], S[a][x] - G[x][y] + S[y][b]);
                    }
                }
            }
        }

        // Sをダブリングの手法で更新していく
        while (0 < charges) {
            //- 現在のDをSに反映できるのであれば、Sを更新する
            if ((charges & 1) == 1) {
                //-- Dを使ってSを更新(S2に一時格納)
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        for (int k = 0; k < N; k++) {
                            S2[j][k] = min(S2[j][k], S[j][i] + D[i][k]);
                        }
                    }
                }
                //-- S2をSにコピー
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        S[i][j] = S2[i][j];
                    }
                }
            }

            //- Dをダブリング
            //- パワー使用回数を2^nから2^(n+1)にする(D2に一時格納)
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    for (int k = 0; k < N; k++) {
                        D2[j][k] = min(D2[j][k], D[j][i] + D[i][k]);
                    }
                }
            }
            //- D2をDにコピー
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    D[i][j] = D2[i][j];
                }
            }

            //- 使用回数を更新
            charges >>= 1;
        }

        // 答えを返す
        return S[0][N - 1];
    }
};