SRM579 Div1 Medium

450

DP[どこを巡った][今どこ] = 最短時間
O(2^N * N)

前もって全点間最短距離を計算しておく。

const int V = 50 + 5;
lli g[V][V];

const lli inf = 604800 * 5;

struct S {
  lli begin, end, dur;
};
S store[V];

const int M = 16;
const int BIT = 1 << M;

const lli L = 604800;

class TravellingPurchasingMan {
public:
  int maxStores(int N, vector <string> inter, vector <string> R)
  {
    fill(&g[0][0], &g[V - 1][V - 1] + 1, inf);

    for (int i = 0; i < R.size(); ++i) {
      istringstream iss(R[i]);
      lli a, b, len;
      iss >> a >> b >> len;
      g[a][b] = g[b][a] = min(g[a][b], len);
    }

    for (int i = 0; i < inter.size(); ++i) {
      istringstream iss(inter[i]);
      iss >> store[i].begin >> store[i].end >> store[i].dur;
    }

    for (int i = 0; i < N; ++i) {
      g[i][i] = 0;
    }
    for (int k = 0; k < N; ++k) {
      for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
          g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
        }
      }
    }

    const int m = inter.size();

    const int BIT = 1 << M;
    static lli dp[BIT][M];
    fill(&dp[0][0], &dp[BIT - 1][M - 1] + 1, inf);

    for (int i = 0; i < m; ++i) {
      if (g[N - 1][i] <= store[i].end) {
        dp[1 << i][i] = g[N - 1][i];
      }
    }

    const int B = 1 << m;
    for (int bit = 0; bit < B; ++bit) {
      for (int curr = 0; curr < m; ++curr) {
        if (bit & (1 << curr)) {
          unless (dp[bit][curr] <= store[curr].end) continue;
          for (int next = 0; next < m; ++next) {
            unless (bit & (1 << next)) {
              lli p = max(store[curr].begin, dp[bit][curr]) + store[curr].dur;
              lli c = p + g[curr][next];

              lli& ref = dp[bit | (1 << next)][next];
              ref = min(ref, c);
            }
          }
        }
      }
    }

    int mx = 0;
    for (int bit = 0; bit < BIT; ++bit) {
      int bc = __builtin_popcount(bit);
      for (int i = 0; i < M; ++i) {
        if (dp[bit][i] <= store[i].end) mx = max(mx, bc);
      }
    }
    return mx;
  }