Solution UVA: 216 - Getting in Line

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss216 - Getting in Line	Accepted	C++11	0.000	0.000	761	2 mins ago

Suggest:

Throw away the TSP dynamic programming algorithm and we will have a super easy recursive + branch and bound problem

#include<bits/stdc++.h>

#define X first

#define Y second

using namespace std;

double sum;

int n, cnt;

double res;

vector<int> child(9);

vector<int> trace(9);

vector<bool> visited(9);

vector<pair<int, int>> a(9);

double dist(int u, int v){

    return sqrt((a[u].X-a[v].X)*(a[u].X-a[v].X) + (a[u].Y-a[v].Y)*(a[u].Y-a[v].Y)) + 16;    

}

void dfs(int u, double sum){

   

    if (sum > res) return;

    bool finish= true;

    for(int v=1; v<=n; v++)

        if (v!=u and not visited[v]){

            finish= false;

           

            child[u]= v;

            visited[v]= true;

                dfs(v, sum + dist(u,v));

            visited[v]= false;

            child[u]= 0;

        }

   

    if (finish) {

        if (res > sum){

            res= sum;

            trace= child;      

        }  

    }

}

void f(int par, int chi){

    if (chi==0) return;

    cout<<"Cable requirement to connect ("<<a[par].X<<","<<a[par].Y<<") to ("<<a[chi].X<<","<<a[chi].Y<<") is "<<fixed<<setprecision(2)<<dist(par, chi)<<" feet.\n";

    f(chi, trace[chi]);

}

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

    while(cin >> n && n){

       

        for(int i=1; i<=n; i++)

            cin >> a[i].X >> a[i].Y;

       

        res= 1000111000;

       

        for(int i=1; i<=n; i++){

       

            sum= 0;

            for(int j=1; j<=n; j++) visited[j]= false;

            for(int j=1; j<=n; j++) child[j]= 0;

           

            visited[i]= true;

            child[0]= i;

            dfs(i, 0);

        }

           

        cout<<"**********************************************************\n";

        cout<<"Network #"<<++cnt<<"\n";

        f(trace[0], trace[trace[0]]);

        cout<<"Number of feet of cable required is "<<fixed<<setprecision(2)<<res<<".\n";

    }

}