Travelling Salesman Problem Spoj







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;

}



Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge.
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment