Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- vector<vector<int>> adj;
- int oo = 1e9;
- vector<vector<int>> dp;
- int tsp(int m, int i)
- {
- if(dp[m][i]!=-1) return dp[m][i];
- if(m==(1<<adj.size())-1) return adj[i][0];
- int min_dist = oo;
- for(int j=0;j<adj.size();j++)
- {
- bool vis = (m>>j)&1;
- if(!vis) min_dist = min( min_dist, adj[i][j] + tsp(m | (1<<j), j) );
- }
- return dp[m][i] = min_dist;
- }
- int tsp()
- {
- int n = adj.size();
- dp.assign(1<<n, vector<int>(n, -1));
- return tsp(1,0);
- }
- int main()
- {
- adj = { {0,10,15,20},
- {10,0,35,25},
- {15,35,0,30},
- {20,25,30,0}
- };
- cout << tsp() << " (Expect: 80) \n";
- }
Advertisement
Add Comment
Please, Sign In to add comment