请教一下dfs的做法
  • 板块P1433 吃奶酪
  • 楼主KidA
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/11/12 13:42
  • 上次更新2023/10/27 03:16:48
查看原帖
请教一下dfs的做法
542221
KidA楼主2022/11/12 13:42

我的这个dfs+剪枝交上去被hack了,请大佬们帮忙看看怎样才能不被hack?

代码如下:

#include<bits/stdc++.h>
using namespace std;
int n,Tme=0;
double x[16],y[16],dis[16][16];
double ans;
bool vis[16];
double calcDis(double X1,double Y1,double X2,double Y2){
    return sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2));
}
void dfs(int deep,int now,double sum){
    Tme++;
    if(Tme>=10000000){
        cout<<setprecision(2)<<fixed<<ans;
        exit(0);
    }
    if(deep>n){
        if(sum<ans) ans=sum;
        return;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            double nxt=sum+dis[now][i];
            if(nxt>=ans) continue;
            vis[i]=true;
            dfs(deep+1,i,nxt);
            vis[i]=false;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    ans=1e6;
    x[0]=0;y[0]=0;
    for(int i=1;i<=n;i++)
        cin>>x[i]>>y[i];
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            dis[i][j]=calcDis(x[i],y[i],x[j],y[j]);
    dfs(1,0,0);
    cout<<setprecision(2)<<fixed<<ans;
    return 0;
}
2022/11/12 13:42
加载中...