SRM407 Div2 Hard

1000

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

view plainprint?

1. class CheapestRoute {  
2. public:  
3.   vector <int> routePrice(vector <int> P, vector <int> enter, vector <int> exit, int T)  
4.   {  
5.     const int N = 50 + 2;  
6.     lli dp[N][N][N];  
7.   
8.     const lli inf = 1LL << 60;  
9.     fill(&dp[0][0][0], &dp[N - 1][N - 1][N], inf);  
10.     dp[0][0][0] = 0;  
11.   
12.     const int n = P.size();  
13.   
14.     for (int i = 0; i + 1 < (int)n; ++i) {  
15.       for (int j = 0; j < (int)n; ++j) {  
16.         for (int k = 0; k < (int)n; ++k) {  
17.           if (dp[i][j][k] == inf) continue;  
18.           if (j + 1 < n && P[j + 1] != -1) {  
19.             dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k], dp[i][j][k] + P[j + 1]);  
20.           }  
21.           if (j && P[j - 1] != -1) {  
22.             dp[i + 1][j - 1][k] = min(dp[i + 1][j - 1][k], dp[i][j][k] + P[j - 1]);  
23.           }  
24.           for (int l = 0; l < (int)enter.size(); ++l) {  
25.             if (enter[l] == j && P[exit[l]] != -1) {  
26.               dp[i + 1][exit[l]][k + 1] = min(dp[i + 1][exit[l]][k + 1], dp[i][j][k] + k + T);  
27.             }  
28.           }  
29.         }  
30.       }  
31.     }  
32.   
33.     vector<int> ret;  
34.     lli M = inf;  
35.     lli C = inf;  
36.     for (int i = 0; i < (int)N; ++i) {  
37.       for (int j = 0; j < (int)N; ++j) {  
38.         C = min(C, dp[i][n - 1][j]);  
39.       }  
40.     }  
41.     if (C == inf) return ret;  
42.   
43.     for (int i = 0; i < (int)N; ++i) {  
44.       for (int j = 0; j < (int)N; ++j) {  
45.         if (dp[i][n - 1][j] == C) {  
46.           M = min(M, (lli)i);  
47.         }  
48.       }  
49.     }  
50.   
51.     ret.push_back(C);  
52.     ret.push_back(M);  
53.     return ret;  
54.   }  
55. };  

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