WARush

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

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