Guest User

Untitled

a guest
Dec 8th, 2019
132
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