SRM626 Div2 Hard "NegativeGraphDiv2"
問題
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 <= 2500
考えたこと
c回パワーを使ったときの1からtへの最短コストは、以下2つの可能性が考えられる。
1. c回パワーを使った時の1からsへの最短コストに、sからtへの最小エッジの重みを足したもの 2. c-1回パワーを使ったときの1からsへの最短コストに、sからtへの最大エッジの重みを引いたもの
負の閉路があるため、ベルマンフォード法を使ってだしてやる
ソースコード
const long long INF = 50 * 100000 + 50; /* D[i][j] := i回パワーを使ったときの1からj+1へ移動するための最小コスト */ long long D[1050][55]; int cnt[55], val[55]; class NegativeGraphDiv2 { 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]--; } // 初期化 for (int c = 0; c <= 100; c++) { for (int i = 0; i < N; i++) { D[c][i] = INF; } } D[0][0] = 0; // ベルマンフォード法で最短距離を更新 for (int c = 0; c <= charges; c++){ while (true) { bool update = false; for (int i = 0; i < from.size(); i++) { int a = from[i]; int b = to[i]; int w = weight[i]; if (D[c][a] != INF && D[c][b] > D[c][a] + w) { D[c][b] = D[c][a] + w; update = true; } if (c != 0 && D[c - 1][a] != INF && D[c][b] > D[c - 1][a] - w) { D[c][b] = D[c - 1][a] - w; update = true; } } if (!update) break; } } // 答えを返す long long res = INF; for (int c = 0; c <= charges; c++) { res = min(res, D[c][N - 1]); } return res; } };