fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <utility>
  6. #include <numeric>
  7. #include <cstring>
  8. #include <cmath>
  9. #include <functional>
  10. #include <vector>
  11. #include <map>
  12. #include <set>
  13. #include <stack>
  14. #include <queue>
  15. #include <iomanip>
  16. #include <sstream>
  17. #include <cassert>
  18.  
  19. using namespace std;
  20.  
  21. #define y0 fsdjkfsdkf
  22. #define y1 gfsdkjfsdjk
  23. #define next fsdkjfsdjk
  24. #define link dfkfsdjkfsk
  25.  
  26. int n, k, i, j, h, nx;
  27. int a[200], g[200];
  28. bool mar[200];
  29. int d[200][200];
  30. int bb[1<<19];
  31. int f[320000][19];
  32.  
  33. int calc(int x) {
  34.     int ret = 0;
  35.     while (x) {
  36.         ret += (x & 1);
  37.         x /= 2;
  38.     }
  39.     return ret;
  40. }
  41.  
  42. int main() {
  43.     freopen("run.in", "r", stdin);
  44.     freopen("run.out", "w", stdout);
  45.     ios_base::sync_with_stdio(0);
  46.  
  47.     cin >> n >> k;
  48.     for (int i = 1; i <= k; i++) {
  49.         cin >> a[i];
  50.         g[i] = g[i - 1] + a[i];
  51.         mar[g[i]] = 1;
  52.     }
  53.     for (int i = 0; i <= n; i++) {
  54.         for (int j = 0; j <= n; j++) {
  55.             cin >> d[i][j];
  56.         }
  57.     }
  58.     h = (1 << n) - 1;
  59.     for (int i = 0; i <= h; i++)
  60.     for (int j = 0; j <= n; j++) f[i][j] = (int)1e9;
  61.     for (int i = 0; i <= h; i++) bb[i] = calc(i);
  62.     f[0][0] = 0;
  63.     for (int i = 0; i <= h; i++)
  64.     for (int j = 0; j <= n; j++) if (f[i][j] < (int)1e9) {
  65.         for (int nx = 1; nx <= n; nx++) {
  66.             if (i & (1 << (nx - 1))) continue;
  67.             if (mar[bb[i] + 1]) {
  68.                f[i ^ (1 << (nx - 1))][0] = min(f[i ^ (1 << (nx - 1))][0], f[i][j] + d[j][nx] + d[nx][0]);
  69.             } else {
  70.                f[i ^ (1 << (nx - 1))][nx] = min(f[i ^ (1 << (nx - 1))][nx], f[i][j] + d[j][nx]);
  71.             }
  72.         }
  73.     }
  74.     cout << f[h][0] << endl;
  75.  
  76.     return 0;
  77. }
Runtime error #stdin #stdout #stderr 0s 29408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure'
  what():  basic_filebuf::underflow error reading the file
https://ideone.com/J0S8DC
language:
C++14 (gcc 8.3)
created:
8 years 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!