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