WARush

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

Codeforces #179 Div2 D "Greg and Graph"

問題

http://codeforces.com/contest/296/problem/D

頂点がn個の重み付き有向グラフが与えられる。
このグラフの任意の2つの頂点V,Uには、
VからUへと向かう辺と、UからVへと向かう辺がそれぞれ存在する。
このグラフを使って、以下のような操作を行う

操作はn回行う。
各操作では、頂点を1つ削除するとともに、
そこに入っている、またはそこから出ている辺も削除する。
各操作でどの頂点を削除するかは、あらかじめリストが与えられる。
各操作の前に、残っている頂点において、
任意の2頂点の全てのペアの最短距離の合計を出力せよ。

制約

1 <= n <= 500
1 <= 任意の2頂点vからuの距離 <= 10^5



考えた事

頂点を削除していくと考えるとめんどくさいので、
頂点0の状態から、1つずつ追加していくと考える。

追加された頂点をAとすると、
1. まずAから既にあった頂点への最短距離をダイクストラで求める。

2. 次に既にあった頂点からAへの最短距離をダイクストラで求める。

3. 最後に既にあった頂点同士の最短距離を以下のように更新する。
既にあった2つの頂点をV,Uとすると、
V→Uの最短距離はV→UまたはV→A→Uのどちらかなので、
これの最小をとっていく。

1.2. はO( E log V )
3. はO( V^2 )なので、
合計O( E log V + V^2 )になる(?)
E log V + V^2 = 25000 * 9 + 25000 = 最大27万くらい。
それを最大500回やるのでいちおくさんぜん・・アレ?

頂点が少ないときとかもっと落ちるし大丈夫。

模範解答

辺Kを追加していくと言う事は、
V→Uに向かうにあたって、今から辺Kを使ってもいいよ!
と、いっているのと同じ事である。

これは、ワーシャル-フロイド法の過程そのままなので、
ワーシャル-フロイド法をやりつつ、
各Kにおいて、結果を出力していけばよい。

計算量はO( V^3 )


ソースコード

int N;
int G[510][510];
int rmv[510];
long long sum[510];

int main() {

    // 入力
    cin >> N;
    for( int i = 1; i <= N; i++ ){
        for( int j = 1; j <= N; j++ ){
            cin >> G[i][j];
        }
    }
    for( int i = 1; i <= N; i++ ){
        cin >> rmv[i];
    }
    reverse( rmv + 1, rmv + 1 + N );

    // ワーシャル-フロイド法
    for( int n = 1; n <= N; n++ ){
        int k = rmv[n];
        
        for( int i = 1; i <= N; i++ ){
            for( int j = 1; j <= N; j++ ){
                G[i][j] = min( G[i][j], G[i][k] + G[k][j] );
            }
        }

        // 各ステップで最短距離の合計を記録
        sum[n] = 0;
        for( int i = 1; i <= n; i++ ){
            for( int j = 1; j <= n; j++ ){
                sum[n] += G[rmv[i]][rmv[j]];
            }
        }
    }

    // 出力
    for( int i = N; i >= 1; i-- ){
        printf( "%I64d ", sum[i] );
    }

    return 0;
}