Problem Link: https://www.spoj.com/problems/PESADA04/
#include <bits/stdc++.h>
using namespace std;
int tsp(vector<vector<int> > graph, int s,int N)
{
// store all vertex apart from source vertex
vector<int> vertex;
for (int i=0; i<N; i++)
{
if(i!=s)
{
vertex.push_back(i);
}
}
// store minimum weight Hamiltonian Cycle.
int min_path = INT_MAX;
do
{
// store current Path weight(cost)
int current_pathweight = 0;
// compute current path weight
int k = s;
for (int i = 0; i <vertex.size(); i++)
{
current_pathweight += graph[k][vertex[i]];
//cout<<k<<" "<<vertex[i]<<"="<<graph[k][vertex[i]]<<endl;
k = vertex[i];
}
current_pathweight += graph[k][s]; //for looping back to source 4 1
//cout<<current_pathweight<<endl;
// update minimum
min_path = min(min_path, current_pathweight);
}while(next_permutation(vertex.begin(), vertex.end()));
return min_path;
}
int main()
{
long long int i,j,k,l,m,n,s=0,t,u,v;
cin>>t;
for(k=1;k<=t;k++)
{
vector<vector<int> > g;
cin>>n;
m=n+1;
u=0;
for(i=0;i<m;i++)
{
vector<int>row;
for(j=0;j<n;j++)
{
cin>>v;
row.push_back(v);
}
auto itpos=row.begin()+u;
row.insert(itpos,0);
g.push_back(row);
u++;
}
/*for(i=0;i<m;i++)
{
for(j=0;j<m;j++)
{
cout<<g[i][j]<<" ";
}
cout<<endl;
}*/
cout << tsp(g,s,m) << endl;
}
return 0;
}
0 comments:
Post a Comment