### 216 - Getting in Line

Posted:

**Fri Jun 14, 2002 2:55 am**Works for all test cases. WAs! Please help. Thanks!

[cpp]#include <stdio.h>

#include <vector>

#include <algorithm>

#include <math.h>

using namespace std;

double df(double a,double b)

{

return sqrt(a*a+b*b);

}

void main()

{

int i,j,N,z;

vector<vector<double> > dist;

vector<pair<int,int> > points;

vector<int> enumeration,ShortestPath;

double Shortest,Current;

z=0;

while(scanf("%d",&N)!=EOF&&N>0)

{

z++;

dist=vector<vector<double> >(N,vector<double>(N,0));

points.resize(N);

enumeration.clear();

Shortest=100000;

for(i=0;i<N;i++)

{

scanf("%d%d",&points

[cpp]#include <stdio.h>

#include <vector>

#include <algorithm>

#include <math.h>

using namespace std;

double df(double a,double b)

{

return sqrt(a*a+b*b);

}

void main()

{

int i,j,N,z;

vector<vector<double> > dist;

vector<pair<int,int> > points;

vector<int> enumeration,ShortestPath;

double Shortest,Current;

z=0;

while(scanf("%d",&N)!=EOF&&N>0)

{

z++;

dist=vector<vector<double> >(N,vector<double>(N,0));

points.resize(N);

enumeration.clear();

Shortest=100000;

for(i=0;i<N;i++)

{

scanf("%d%d",&points

*.first,&points**.second);*

}

for(i=0;i<N;i++)

{

for(j=0;j<N;j++)

{

if(i!=j)

{

dist}

for(i=0;i<N;i++)

{

for(j=0;j<N;j++)

{

if(i!=j)

{

dist

*[j]=df(points**.first-points[j].first,points**.second-points[j].second)+16;*

}

}

}

for(i=0;i<N;i++)

{

enumeration.push_back(i);

}

do

{

Current=0;

for(i=1;i<N;i++)

{

Current+=dist[enumeration[i-1]][enumeration}

}

}

for(i=0;i<N;i++)

{

enumeration.push_back(i);

}

do

{

Current=0;

for(i=1;i<N;i++)

{

Current+=dist[enumeration[i-1]][enumeration

*];*

}

if(Current<Shortest)

{

Shortest=Current;

ShortestPath=enumeration;

}

}

while(next_permutation(enumeration.begin(),enumeration.end()));

printf("**********************************************************\n");

printf("Network #%d\n",z);

for(i=1;i<N;i++)

{

printf("Cable requirement to connect (%d,%d) to (%d,%d) is %3.2lf feet.\n",points[ShortestPath[i-1]].first,points[ShortestPath[i-1]].second,points[ShortestPath}

if(Current<Shortest)

{

Shortest=Current;

ShortestPath=enumeration;

}

}

while(next_permutation(enumeration.begin(),enumeration.end()));

printf("**********************************************************\n");

printf("Network #%d\n",z);

for(i=1;i<N;i++)

{

printf("Cable requirement to connect (%d,%d) to (%d,%d) is %3.2lf feet.\n",points[ShortestPath[i-1]].first,points[ShortestPath[i-1]].second,points[ShortestPath

*].first,points[ShortestPath**].second,dist[ShortestPath[i-1]][ShortestPath**]);*

}

printf("Number of feet of cable required is %3.2lf.\n",Shortest);

}

}[/cpp]}

printf("Number of feet of cable required is %3.2lf.\n",Shortest);

}

}[/cpp]