216 - Getting in Line

Problem Link

#include<bits/stdc++.h>
using namespace std;
#define MAX 10

int n;
vector<int>path;
double dist[MAX][MAX];

double TSP()
{
    vector<int>vertex;
    for(int i = 1; i <= n; i++)
            vertex.push_back(i);
    double min_path = numeric_limits<double>::max();

    do
    {
        double curr_pathweight = 0.0;
        for(int i = 0; i < vertex.size(); i++)
        {
            curr_pathweight += dist[vertex[i]][vertex[i+1]];
        }
        if(min_path > curr_pathweight)
        {
            min_path = curr_pathweight;
            path = vertex;
        }
    }
    while(next_permutation(vertex.begin(), vertex.end()));

    return min_path;
}


int main()
{
    int test = 0;
    while(cin>>n && n)
    {
        memset(dist, 0.0, sizeof(dist));
        double x[10], y[10];
        for(int i = 1; i <= n; i++)
            cin>>x[i]>>y[i];
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dist[i][j] = sqrt(((x[i]-x[j]) * (x[i] - x[j])) + ((y[i] - y[j]) * (y[i] - y[j]))) + 16.00;
            }
        }
        cout<<"**********************************************************"<<endl;
        cout<<"Network #"<< ++test<<endl;
        double ans = TSP();
        for(int i = 0; i < path.size()-1; i++)
        {
            int pin = path[i];
            int pin1 = path[i+1];
            cout<<fixed<<setprecision(2)<<"Cable requirement to connect ("<<(int)x[pin]<<","<<(int)y[pin]<<") to ("<<(int)x[pin1]<<","<<(int)y[pin1]<<") is "<<dist[pin][pin1]<<" feet."<<endl;
        }
        cout<<fixed<<setprecision(2)<<"Number of feet of cable required is "<<ans<<"."<<endl;
    }

    return 0;
}