BFS40TLE
  • 板块P1433 吃奶酪
  • 楼主rqsg
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/3/16 18:36
  • 上次更新2023/10/23 21:24:08
查看原帖
BFS40TLE
748469
rqsg楼主2023/3/16 18:36
#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
using namespace std;

vector<  pair< long long ,double >  > vec [20];


long long N;long long x1,y2;

double minn=9999999;
bool bas[200];
struct abc{
	long long x;
	double y;
}num[200];


void bfs(long long i,long long now,double ans){
//	cout<<i<<" "<<now<<" "<<ans<<endl;
	
	if(i==N) {
		minn=min(minn,ans);
//		cout<<"minn==  "<<minn;cout<<endl;
		return ;
	}
	
	for(long long iter=0;iter<vec[now].size();iter++){
		long long to=vec[now][iter].first;
		double s=vec[now][iter].second;
		
		if(!bas[to]){
			bas[to]=1;ans+=s;
			bfs(i+1,to,ans);
			bas[to]=0;ans-=s;
		}
		
	}
	
	
	
	return ;
}


int main(){
	
	cin>>N;
	for(long long i=1;i<=N;i++)
    {
    	cin>>x1>>y2;
    	num[i].x=x1;num[i].y=y2;
    	if(i>=1){
    		for(long long j=0;j<i;j++){
    			double s=sqrt(1.0*((x1-num[j].x)*(x1-num[j].x))+((y2-num[j].y)*(y2-num[j].y)));
    			vec[j].push_back(make_pair(i,s));
    			vec[i].push_back(make_pair(j,s));
    		}
    	}
    }
    
   
   /* for(int i=0;i<=4;i++){
    	cout<<i<<endl;
    	for(int j=0;j<vec[i].size();j++){
    		cout<<vec[i][j].first<<"  ";cout<<vec[i][j].second;
    		cout<<endl;
    	}
    	cout<<endl;cout<<endl;
    }
  */
    

    bas[0]=1;	
    bfs(0,0,0);
	
	printf("%.2lf",minn);
	return 0;
}
2023/3/16 18:36
加载中...