fork download 
  1. #include <bits/stdc++.h>
  2. #define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
  3. using namespace std;
  4.  
  5. mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
  6. int UID(int l, int r){
  7.     uniform_int_distribution<mt19937_64::result_type> R(l, r);
  8.     return R(RNG);
  9. }
  10.  
  11.  
  12. const int maxn = 15;
  13. int n,K,Q;
  14. int d[maxn];
  15. int c[maxn][maxn];
  16.  
  17. vector<int> x[maxn];
  18. vector<vector<int> > x_best;
  19.  
  20. int loaded[maxn];
  21. bool visited[maxn];
  22.  
  23. int f = 0;
  24. int fbest = INT_MAX-1;
  25. int cmin = INT_MAX-1;
  26. int cmin2 = INT_MAX-1;
  27.  
  28. bool can_go_to(int car, int x){
  29.     if (visited[x]) return false;
  30.     if (loaded[car] + d[x] > Q) return false;
  31.     return true;
  32. }
  33.  
  34. void DEBUG(int num_car_using){
  35.     cout << "STEP\n";
  36.     for (int i = 1; i <= num_car_using; i++){
  37.         cout << "BY CAR " << i << ": ";
  38.         for (auto val : x[i]){
  39.             cout << val << " ";
  40.         }
  41.         cout << "\n";
  42.     }
  43.     cout << "\n";
  44. }
  45.  
  46. void update_best(int num_car_using){
  47.     int true_f = f;
  48.     for (int i = 1; i <= num_car_using; i++){
  49.         true_f += c[x[i].back()][0];
  50.     }
  51.     if (fbest > true_f){
  52.         x_best.resize(num_car_using+1);
  53.         up(i,1,num_car_using){
  54.             x_best[i].clear();
  55.             x_best[i] = x[i];
  56.         }
  57.         fbest = true_f;
  58.     }
  59. //    DEBUG(num_car_using);
  60. }
  61.  
  62. void TRY_X(int current_car, int num_car_using, int num_node_visited){
  63.     if (num_node_visited == n){
  64.         update_best(num_car_using);
  65.         return;
  66.     }
  67.  
  68.     if (current_car > num_car_using) return;
  69.  
  70.     if (f + (n + num_car_using - num_node_visited)*cmin >= fbest) return;
  71.  
  72. //    cout << "NUM_NODE_VISITED: " << num_node_visited << "\n";
  73. //    DEBUG(num_car_using);
  74.  
  75.     TRY_X(current_car+1, num_car_using, num_node_visited);
  76.  
  77.     for (int v = 1; v <= n; v++){
  78.         if (!can_go_to(current_car, v)) continue;
  79.  
  80.         f += c[x[current_car].back()][v];
  81.         x[current_car].push_back(v);
  82.         visited[v] = true;
  83.         loaded[current_car] += d[v];
  84.  
  85.         TRY_X(current_car, num_car_using, num_node_visited+1);
  86.  
  87.         loaded[current_car] -= d[v];
  88.         visited[v] = false;
  89.         x[current_car].pop_back();
  90.         f -= c[x[current_car].back()][v];
  91.     }
  92. }
  93.  
  94. void TRY_Y(int current_car, int num_car_using, int num_node_visited){
  95.     if (current_car > num_car_using){
  96.         TRY_X(1, num_car_using, num_node_visited);
  97.         return;
  98.     }
  99.  
  100.     if (f + (n + num_car_using - num_node_visited)*cmin >= fbest) return;
  101.  
  102.     for (int start_point = x[current_car-1].back()+1; start_point <= n; start_point++){
  103.         if (!can_go_to(current_car, start_point)) continue;
  104.  
  105.         x[current_car].push_back(start_point);
  106.         visited[start_point] = true;
  107.         loaded[current_car] += d[start_point];
  108.         f += c[0][start_point];
  109.  
  110.         TRY_Y(current_car+1, num_car_using, num_node_visited+1);
  111.  
  112.         f -= c[0][start_point];
  113.         loaded[current_car] -= d[start_point];
  114.         visited[start_point] = false;
  115.         x[current_car].pop_back();
  116.     }
  117. }
  118.  
  119. signed main(){
  120.     ios_base::sync_with_stdio(false);
  121.     cin.tie(0);
  122.     #define Task "A"
  123.     if (fopen(Task".inp", "r")){
  124.         freopen(Task".inp", "r", stdin);
  125.         freopen(Task".out", "w", stdout);
  126.     }
  127.  
  128.     int remain_packages = 0;
  129.     cin >> n >> K >> Q;
  130.     up(i,1,n){
  131.         cin >> d[i];
  132.         remain_packages += d[i];
  133.     }
  134.     up(i,0,n) up(j,0,n) {
  135.         cin >> c[i][j];
  136.         if (i != j) {
  137.             if (c[i][j] <= cmin){
  138.                 cmin2 = cmin;
  139.                 cmin = c[i][j];
  140.             }
  141.             else if (c[i][j] <= cmin2){
  142.                 cmin2 = c[i][j];
  143.             }
  144. //            cmin = min(cmin, c[i][j]);
  145.         }
  146.     }
  147.  
  148.     cmin = (cmin + cmin2)/2;
  149.  
  150.     x[0].push_back(0);
  151.     for (int num_car_using = 1; num_car_using <= K; num_car_using++){
  152. //        cout << "PHASE " << num_car_using << "\n";
  153.         if (Q*num_car_using < remain_packages) continue;
  154.         TRY_Y(1, num_car_using, 0);
  155. //        cout << "\n";
  156.     }
  157.  
  158.     cout << fbest << "\n";
  159.  
  160.  
  161. //    for (int i = 1; i < (int)x_best.size(); i++){
  162. //        cout << "BY CAR " << i << ": ";
  163. //        for (auto u : x_best[i]) cout << u << " ";
  164. //        cout << "\n";
  165. //    }
  166. }
  167.  
Success #stdin #stdout 0.76s 5320KB
comments (?)
stdin 
12 5 27
19 4 13 4 10 7 17 3 5 15 20 11
0 13 10 12 13 13 13 13 13 12 12 14 14
12 0 14 13 11 10 12 13 10 10 11 13 11
12 12 0 13 13 13 13 12 12 12 14 12 10
14 12 14 0 13 12 13 12 11 11 12 10 14
13 13 11 11 0 11 14 11 10 11 12 11 10
13 10 10 14 11 0 10 11 14 12 11 12 12
10 13 14 10 13 12 0 13 14 11 11 14 11
13 14 12 13 11 12 10 0 13 13 14 13 12
10 13 10 12 10 14 10 13 0 12 11 13 11
11 14 13 14 12 14 14 10 13 0 11 14 11
14 14 14 14 13 10 12 14 10 13 0 13 13
12 10 10 10 14 13 10 14 12 13 13 0 13
11 14 12 14 11 10 11 13 12 13 12 11 0
stdout 
194
https://ideone.com/RRoPBW
CVRP with simple BnB
language:
C++14 (gcc 8.3)
created:
72 days ago
visibility:
secret

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!