SRM407 Div2 Hard

1000

dp [ i 回移動した ] [ 今 j にいる ] [ k 回テレポートした ] = 最小コスト

class CheapestRoute {
public:
  vector <int> routePrice(vector <int> P, vector <int> enter, vector <int> exit, int T)
  {
    const int N = 50 + 2;
    lli dp[N][N][N];

    const lli inf = 1LL << 60;
    fill(&dp[0][0][0], &dp[N - 1][N - 1][N], inf);
    dp[0][0][0] = 0;

    const int n = P.size();

    for (int i = 0; i + 1 < (int)n; ++i) {
      for (int j = 0; j < (int)n; ++j) {
        for (int k = 0; k < (int)n; ++k) {
          if (dp[i][j][k] == inf) continue;
          if (j + 1 < n && P[j + 1] != -1) {
            dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k], dp[i][j][k] + P[j + 1]);
          }
          if (j && P[j - 1] != -1) {
            dp[i + 1][j - 1][k] = min(dp[i + 1][j - 1][k], dp[i][j][k] + P[j - 1]);
          }
          for (int l = 0; l < (int)enter.size(); ++l) {
            if (enter[l] == j && P[exit[l]] != -1) {
              dp[i + 1][exit[l]][k + 1] = min(dp[i + 1][exit[l]][k + 1], dp[i][j][k] + k + T);
            }
          }
        }
      }
    }

    vector<int> ret;
    lli M = inf;
    lli C = inf;
    for (int i = 0; i < (int)N; ++i) {
      for (int j = 0; j < (int)N; ++j) {
        C = min(C, dp[i][n - 1][j]);
      }
    }
    if (C == inf) return ret;

    for (int i = 0; i < (int)N; ++i) {
      for (int j = 0; j < (int)N; ++j) {
        if (dp[i][n - 1][j] == C) {
          M = min(M, (lli)i);
        }
      }
    }

    ret.push_back(C);
    ret.push_back(M);
    return ret;
  }
};