dzungchaos

C++ "Untitled tsp_bbcpp"

Jan 15th, 2020
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <limits.h>
  4. using namespace std;
  5. #define MAXN 20
  6. int n, c[MAXN][MAXN] = {}, x[MAXN], xopt[MAXN];
  7. int fk, fopt = INT_MAX , cmin = INT_MAX;
  8.  
  9. void input(){
  10.     cin >> n;
  11.     for(int i = 1; i <= n; i++)
  12.         for(int j = 1; j <= n; j++){
  13.             cin >> c[i][j];
  14.             if (i != j)
  15.                 cmin = cmin > c[i][j] ? c[i][j]:cmin;
  16.         }
  17. }
  18.  
  19. int UCV(int y, int k){
  20.     for(int i = 2; i < k; i++)
  21.         if (y == x[i]) return 0;
  22.     return 1;
  23. }
  24.  
  25. void TRY(int k){
  26.     for(int y = 2; y <= n; y++){
  27.         if (UCV(y, k)){
  28.             x[k] = y;
  29.             fk += c[x[k-1]][y];
  30.             if (k == n){
  31.                 if (fk + c[x[k]][1] < fopt){
  32.                     fopt = fk + c[x[k]][1];
  33.                     for(int i = 1; i <= n; i++)
  34.                         xopt[i] = x[i];
  35.                 }
  36.             } else
  37.             if (fk + cmin * (n - k + 1) < fopt) TRY(k + 1);
  38.             fk -= c[x[k-1]][y];    
  39.         }
  40.     }
  41. }
  42.  
  43. int main(){
  44.     freopen("input.txt", "r", stdin);
  45.     input();
  46.     x[1] = 1; fk = 0;
  47.     TRY(2);
  48.     for (int i = 1; i <= n; i++)
  49.         cout << xopt[i] << " -> ";
  50.     cout << " 1 " << endl;
  51.     cout << "min cost = " << fopt << endl;
  52.     return 0;
  53. }
  54.  
  55.  
  56. INPUT e.g:
  57. 5
  58. 0 3 14 18 15
  59. 3 0 4 22 20
  60. 17 9 0 16 4
  61. 9 20 7 0 18
  62. 9 15 11 5 0
Advertisement
Add Comment
Please, Sign In to add comment