SHARE
TWEET

Untitled

a guest Dec 8th, 2019 101 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdbool.h>
  3.  
  4. int n, s;
  5. int G[20][20];
  6. int box[20];
  7. bool use[20];
  8. int ans = 0x3f3f3f3f;
  9.  
  10. void permutation(int idx) {
  11.     if (idx == n) {
  12.         int dist = 0;
  13.         for (int i = 1; i <= n; i++)
  14.             dist += G[box[i - 1]][box[i]];
  15.         if (dist < ans)
  16.             ans = dist;
  17.         return;
  18.     }
  19.     for (int i = 1; i <= n; i++) {
  20.         if (!use[i]) {
  21.             use[i] = true;
  22.             box[idx] = i;
  23.             permutation(idx + 1);
  24.             use[i] = false;
  25.         }
  26.     }
  27. }
  28.  
  29. int main() {
  30.     scanf("%d%d", &n, &s);
  31.     for (int i = 1; i <= n; i++)
  32.         for (int j = 1; j <= n; j++)
  33.             scanf("%d", &G[i][j]);
  34.  
  35.     box[0] = s;
  36.     box[n] = s;
  37.     use[s] = true;
  38.     permutation(1);
  39.     printf("%d\n", ans);
  40.     return 0;
  41. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top