fork download
copy 
  1. // SIGMA BOY hihihihihihihi
  2.  
  3. #define se second
  4. #define fi first
  5. #define pb push_back
  6. #define pob pop_back
  7. #define bitebi __builtin_popcountll
  8. #include <bits/stdc++.h>
  9. using namespace std;
  10. typedef long long ll;
  11. typedef long double ld;
  12. typedef pair<ll,ll> pll;
  13.  
  14. const ll oo = 1e18;
  15.  
  16. int n, K;
  17. int c[25][25];
  18. int appear[25];
  19. int x[25];
  20. int load;
  21. ll best = oo, f = 0;
  22. ll cmin = oo;
  23.  
  24. void Try(int k) {
  25.     for (int v = 1; v <= 2 * n; v++) {
  26.         if (!appear[v]) {
  27.             // Kiểm tra hợp lệ
  28.             if (v <= n) {
  29.                 if (load < K) { // điểm đón
  30.                     appear[v] = 1;
  31.                     load++;
  32.                     f += c[x[k-1]][v];
  33.                     if (f + (2*n - k + 1) * cmin < best) {
  34.                         x[k] = v;
  35.                         if (k == 2 * n) {
  36.                             best = min(best, f + c[v][0]);
  37.                         } else Try(k + 1);
  38.                     }
  39.                     f -= c[x[k-1]][v];
  40.                     load--;
  41.                     appear[v] = 0;
  42.                 }
  43.             } else {
  44.                 int u = v - n;
  45.                 if (appear[u]) { // chỉ trả nếu đã đón
  46.                     appear[v] = 1;
  47.                     load--;
  48.                     f += c[x[k-1]][v];
  49.                     if (f + (2*n - k + 1) * cmin < best) {
  50.                         x[k] = v;
  51.                         if (k == 2 * n) {
  52.                             best = min(best, f + c[v][0]);
  53.                         } else Try(k + 1);
  54.                     }
  55.                     f -= c[x[k-1]][v];
  56.                     load++;
  57.                     appear[v] = 0;
  58.                 }
  59.             }
  60.         }
  61.     }
  62. }
  63.  
  64. void Do() {
  65.     ios::sync_with_stdio(false);
  66.     cin.tie(nullptr);
  67.  
  68.     cin >> n >> K;
  69.     for (int i = 0; i <= 2*n; i++)
  70.         for (int j = 0; j <= 2*n; j++) {
  71.             cin >> c[i][j];
  72.             if (i != j) cmin = min(cmin, (ll)c[i][j]);
  73.         }
  74.  
  75.     f = 0;
  76.     best = oo;
  77.     load = 0;
  78.     memset(appear, 0, sizeof(appear));
  79.  
  80.     x[0] = 0; // start from depot
  81.     Try(1);
  82.  
  83.     cout << best << "\n";
  84. }
  85.  
  86. signed main() {
  87.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  88. #define task "test"
  89.     if (fopen(task".inp", "r")) {
  90.         freopen(task".inp", "r", stdin);
  91.         freopen(task".out", "w", stdout);
  92.     }
  93.     int ntest = 1;
  94.     while (ntest--) Do();
  95.  
  96.     cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  97. }
  98.  
Success #stdin #stdout #stderr 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000000
stderr
copy 
Time elapsed: 5ms
https://ideone.com/S9hhV1
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!