SRM579 Div1 Medium

450

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

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

view plainprint?

1. const int V = 50 + 5;  
2. lli g[V][V];  
3.   
4. const lli inf = 604800 * 5;  
5.   
6. struct S {  
7.   lli begin, end, dur;  
8. };  
9. S store[V];  
10.   
11. const int M = 16;  
12. const int BIT = 1 << M;  
13.   
14. const lli L = 604800;  
15.   
16. class TravellingPurchasingMan {  
17. public:  
18.   int maxStores(int N, vector <string> inter, vector <string> R)  
19.   {  
20.     fill(&g[0][0], &g[V - 1][V - 1] + 1, inf);  
21.   
22.     for (int i = 0; i < R.size(); ++i) {  
23.       istringstream iss(R[i]);  
24.       lli a, b, len;  
25.       iss >> a >> b >> len;  
26.       g[a][b] = g[b][a] = min(g[a][b], len);  
27.     }  
28.   
29.     for (int i = 0; i < inter.size(); ++i) {  
30.       istringstream iss(inter[i]);  
31.       iss >> store[i].begin >> store[i].end >> store[i].dur;  
32.     }  
33.   
34.     for (int i = 0; i < N; ++i) {  
35.       g[i][i] = 0;  
36.     }  
37.     for (int k = 0; k < N; ++k) {  
38.       for (int i = 0; i < N; ++i) {  
39.         for (int j = 0; j < N; ++j) {  
40.           g[i][j] = min(g[i][j], g[i][k] + g[k][j]);  
41.         }  
42.       }  
43.     }  
44.   
45.     const int m = inter.size();  
46.   
47.     const int BIT = 1 << M;  
48.     static lli dp[BIT][M];  
49.     fill(&dp[0][0], &dp[BIT - 1][M - 1] + 1, inf);  
50.   
51.     for (int i = 0; i < m; ++i) {  
52.       if (g[N - 1][i] <= store[i].end) {  
53.         dp[1 << i][i] = g[N - 1][i];  
54.       }  
55.     }  
56.   
57.     const int B = 1 << m;  
58.     for (int bit = 0; bit < B; ++bit) {  
59.       for (int curr = 0; curr < m; ++curr) {  
60.         if (bit & (1 << curr)) {  
61.           unless (dp[bit][curr] <= store[curr].end) continue;  
62.           for (int next = 0; next < m; ++next) {  
63.             unless (bit & (1 << next)) {  
64.               lli p = max(store[curr].begin, dp[bit][curr]) + store[curr].dur;  
65.               lli c = p + g[curr][next];  
66.   
67.               lli& ref = dp[bit | (1 << next)][next];  
68.               ref = min(ref, c);  
69.             }  
70.           }  
71.         }  
72.       }  
73.     }  
74.   
75.     int mx = 0;  
76.     for (int bit = 0; bit < BIT; ++bit) {  
77.       int bc = __builtin_popcount(bit);  
78.       for (int i = 0; i < M; ++i) {  
79.         if (dp[bit][i] <= store[i].end) mx = max(mx, bc);  
80.       }  
81.     }  
82.     return mx;  
83.   }  

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