matbensch

TSP C++

Jan 15th, 2023
168
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.76 KB | Source Code | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. vector<vector<int>> adj;
  8.  
  9. int oo = 1e9;
  10. vector<vector<int>> dp;
  11.  
  12. int tsp(int m, int i)
  13. {
  14.     if(dp[m][i]!=-1) return dp[m][i];
  15.     if(m==(1<<adj.size())-1) return adj[i][0];
  16.  
  17.     int min_dist = oo;
  18.     for(int j=0;j<adj.size();j++)
  19.     {
  20.         bool vis = (m>>j)&1;
  21.         if(!vis) min_dist = min( min_dist, adj[i][j] + tsp(m | (1<<j), j) );
  22.     }
  23.  
  24.     return dp[m][i] = min_dist;
  25. }
  26.  
  27. int tsp()
  28. {
  29.     int n = adj.size();
  30.     dp.assign(1<<n, vector<int>(n, -1));
  31.     return tsp(1,0);
  32. }
  33.  
  34. int main()
  35. {
  36.     adj = { {0,10,15,20},
  37.             {10,0,35,25},
  38.             {15,35,0,30},
  39.             {20,25,30,0}
  40.         };
  41.     cout << tsp() << " (Expect: 80) \n";
  42. }
Advertisement
Add Comment
Please, Sign In to add comment