卡时WA on #12 #13求调
查看原帖
卡时WA on #12 #13求调
1327843
如履薄冰楼主2025/1/1 14:15
#include<bits/stdc++.h>
using namespace std;
int n,timee=0;
double ans=1e9;
double x[1100000],y[1100000],distancee[3500][3500];
bool vis[1100000];
void init(){
    x[0]=y[0]=0;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            distancee[i][j]=sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
        }
    }
}
void dfs(int cur,double tot,int depth){
    timee++;
    if(timee>=1e7){
        cout<<fixed<<setprecision(2)<<ans;
        exit(0);
    }
    if(depth==n+1){
        ans=min(tot,ans);
        return;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            double temp=distancee[cur][i]+tot;
            if(temp<ans){
                vis[i]=true;
                dfs(i,temp,depth+1);
                vis[i]=false;
            }
        }
    }
}
int main(){
	ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    init();
    dfs(0,0,1);
    cout<<fixed<<setprecision(2)<<ans;
    return 0;
}
2025/1/1 14:15
加载中...