暴力搜索只得了50分 TLE了5个点???
查看原帖
暴力搜索只得了50分 TLE了5个点???
490978
小超手123楼主2021/10/7 12:36
#include <bits/stdc++.h> 
using namespace std;
int n;
double ans=999999.99;
double x[20],y[20];
bool vis[20];
double f(double x1,double y1,double x2,double y2){
	return sqrt(pow(x1-x2,2)+pow(y1-y2,2));
}
void dfs(int k,int num,double xx,double yy,double sum){
	if(num>n){
		
		ans=min(ans,sum);
		return;
	}
	for(int i=1;i<=n;i++){
		if(k!=i&&vis[i]==0){
			vis[i]=1;
			dfs(i,num+1,x[i],y[i],sum+f(xx,yy,x[i],y[i]));
			vis[i]=0;
		}
	}
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>x[i]>>y[i];
    
    dfs(0,1,0,0,0);
    printf("%.2f",ans);
    return 0;
} 
2021/10/7 12:36
加载中...