一道ACM题目总是AC不了,求指出错误。。
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=108&problem=152&mosmsg=Submission+received+with+ID+12668984
一道搜索题可以回溯也可以暴力枚举,我用的是暴力枚举,总是WA,样例都通过了,就是找不到原因,求大神指出错误,谢谢啦。
#include<iostream>ACM 回溯
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<cmath>
using namespace std;
int num[10];
int num1[10];
class P
{
public:
int x,y;
}point[10];
double dis(int len)
{
double sum=0;
for(int i=1;i<len;i++)
{
sum=sum+sqrt((point[num[i]].x-point[num[i-1]].x)*(point[num[i]].x-point[num[i-1]].x)+(point[num[i]].y-point[num[i-1]].y)*(point[num[i]].y-point[num[i-1]].y))+16;
}
return sum;
}
int main()
{
int n,k=0;
while(cin>>n&&n)
{
memset(point,0,sizeof(point));
memset(num,0,sizeof(num));
memset(num1,0,sizeof(num1));
int i,j;
for(i=0;i<n;i++)
cin>>point[i].x>>point[i].y;
for(i=0;i<n;i++)
num[i]=i;
double minlen=dis(n);
while(next_permutation(num,num+n))
{
if(dis(n)<minlen)
{
memcpy(num1,num,sizeof(num));
minlen=dis(n);
}
}
cout<<"**********************************************************"<<endl;
cout<<"Network #"<<++k<<endl;
for(i=1;i<n;i++)
{
double d=sqrt((point[num1[i]].x-point[num1[i-1]].x)*(point[num1[i]].x-point[num1[i-1]].x)+(point[num1[i]].y-point[num1[i-1]].y)*(point[num1[i]].y-point[num1[i-1]].y));
cout<<"Cable requirement to connect ("<<point[num1[i-1]].x<<","<<point[num1[i-1]].y<<") to ("<<point[num1[i]].x<<","<<point[num1[i]].y<<") is ";
cout<<fixed<<setprecision(2)<<d+16<<" feet."<<endl;
}
cout<<"Number of feet of cable required is "<<fixed<<setprecision(2)<<minlen<<"."<<endl;
}
return 0;
}