ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

TopCoder SRM 626 Div2 Hard : NegativeGraphDiv2

概要


N個のノードとE本のエッジからなる有向グラフがある。

各ノード間の移動にはコストがかかる時、ノード1からNに到達するための最短コストを求めよ。

ただし、以下の操作をcharges回行うことができる。
・ノード間のコストweightをweight*(-1)にする

解法


(Editorial見た)

まずは負のコストを考えずに各ノード間の最短コストを求めておく。

その後にDPでコストの操作を行ったときの解を求める。
更新式は、
dp[コスト変更の操作をi回以下行った][jからNまで] := 最短コスト
となる。

ソースコード

const lli INFLL = (1LL << 60);

class NegativeGraphDiv2 {
public:

  long long findMin(int N, vector <int> s, vector <int> t, vector <int> weight, int charges) {
    lli dist[50][50];
    
    rep(i, s.size()) {
      s[i]--;
      t[i]--;
    }

    rep(i, N) rep(j, N) {
      dist[i][j] = (i == j) ? 0 : INFLL;
    }
    
    rep(i, s.size()) {
      dist[s[i]][t[i]] = min(dist[s[i]][t[i]], (lli)weight[i]);
    }
    
    rep(k, N) rep(i, N) rep(j, N) {
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    }

    lli dp[1001][50];
    
    rep(i, N) {
      dp[0][i] = dist[i][N - 1];
    }

    REP(i, 1, charges + 1) rep(j, N) {
      dp[i][j] = dp[i - 1][j];
      rep(k, s.size()) {
        dp[i][j] = min(dp[i][j], dist[j][s[k]] + dp[i - 1][t[k]] - weight[k]);
      }
    }

    return dp[charges][0];
  }