我的思路是从原点出发,找到一个离它最近的点,再把最近的那个点作为起点,再找到离起点最近的点,这个思路到底哪里有问题?。。。
#include<bits/stdc++.h>
using namespace std;
int n;
double x[20],y[20];
double dp[205];
bool vis[25];
int idx;
double sum;
double two_dis(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void solve(){
for(int i=0;i<n;i++){
int t=idx;
vis[idx]=true;
dp[i]=1e9;
for(int j=0;j<=n;j++){
if(!vis[j]){
if(two_dis(x[t],y[t],x[j],y[j])<=dp[i]) idx=j;
dp[i]=min(dp[i],two_dis(x[t],y[t],x[j],y[j]));
}
}
}
}
int main(){
cin>>n;
x[0]=0;
y[0]=0;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}
solve();
for(int i=0;i<n;i++){
sum+=dp[i];
}
printf("%.2lf",sum);
}