daily pastebin goal
37%
SHARE
TWEET

Untitled

a guest Jan 22nd, 2018 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cstring>
  4. using namespace std;
  5. const int NN = 17;
  6.  
  7. int n, m;
  8. int w[NN][NN];
  9. int dp[1<<NN];
  10.  
  11. int doit(int mask) {
  12.     if(!mask) return 0;
  13.     if(dp[mask] == -1) {
  14.         int a, b;
  15.         dp[mask] = 0x3f3f3f3f;
  16.         for(a = 0; !(mask&(1<<a)); a++);
  17.         for(b = a+1; b < n; b++) if(mask&(1<<b))
  18.             dp[mask] = min(dp[mask], doit(mask^(1<<a)^(1<<b)) + w[a][b]);
  19.     }
  20.     return dp[mask];
  21. }
  22.  
  23. int main(void) {
  24.     while(scanf("%d", &n) && n) {
  25.         int mask = 0, total = 0;
  26.         for(int i = 0; i < n; i++)
  27.             for(int j = 0; j < n; j++)
  28.                 w[i][j] = (i != j)*0x3f3f3f3f;
  29.         memset(dp, -1, sizeof(dp));
  30.         scanf("%d", &m);
  31.         for(int i = 0; i < m; i++) {
  32.             int a, b, c;
  33.             scanf("%d %d %d", &a, &b, &c), a--, b--;
  34.             w[a][b] = w[b][a] = min(w[a][b], c);
  35.             mask ^= (1<<a)^(1<<b);
  36.             total += c;
  37.         }
  38.         for(int k = 0; k < n; k++)
  39.             for(int i = 0; i < n; i++)
  40.                 for(int j = 0; j < n; j++)
  41.                     w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
  42. /*      int ans = 0x3f3f3f3f;
  43.         for(int i = 0; i < n; i++) if(mask&(1<<i))
  44.             for(int j = 0; j < n; j++) if(mask&(1<<j))
  45.                 ans = min(ans, total+doit(mask^(1<<i)^(1<<j)));
  46.         printf("%d\n", ans)r*/
  47.         printf("%d\n", total+doit(mask));
  48.     }
  49.  
  50.     return 0;
  51. }
RAW Paste Data
Top