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