Problem Link: https://practice.geeksforgeeks.org/problems/travelling-salesman-problem/0
#include <bits/stdc++.h>
using namespace std;
int tsp(long long int graph[100][100], 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]];
k = vertex[i];
}
current_pathweight += graph[k][s]; //for looping back to source 4 1
// 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,g[100][100],s=0,t;
cin>>t;
for(k=1;k<=t;k++)
{
cin>>n;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cin>>g[i][j];
}
}
cout << tsp(g,s,n) << endl;
}
return 0;
}
0 comments:
Post a Comment