P1433 吃奶酪

大致题意:

• 老鼠吃所有奶酪至少要跑多长距离。

基本思路:

• 这真没啥可说的，就一句话，剩下的都在代码里。
• 直接dfs所有的奶酪，寻找最小的就??！

Code:

//早期垃圾码风……见谅
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
using namespace std;
#define ll long long
#define DIS sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))
#define INF 0x7fffffff
int n;
bool pd[1010];
double ans=INF;
double x[20],y[20];
double dis[1010][1010];
void dfs(int cnt,int id,double len){//cnt:吃掉的个数;id:目前所在的点;len:目前走的距离
    if(len>=ans)//剪枝，如果走的距离超过了目前的答案，那么再走也没必要了
        return;
    if(cnt==n){//若是奶酪被全部吃掉了，更新答案
        ans=min(ans,len);
        return;
    }
    for(int i=1;i<=n;++i)//搜索
        if(!pd[i])//若是没有被吃掉就去吃
            pd[i]=1,dfs(cnt+1,i,len+dis[id][i]),pd[i]=0;//搜索&回溯
    return;//额..可有可无
}
int main(){
    scanf("%d",&n);//读入，没啥可说的
    for(int i=1;i<=n;++i)
        scanf("%lf %lf",&x[i],&y[i]);
    for(int i=0;i<=n;++i)//直接记录每两个奶酪的距离
        for(int j=0;j<=n;++j)
            dis[i][j]=DIS;//DIS是个宏定义，上面有鸭
    dfs(0,0,0.0);//搜！
    printf("%.2lf",ans);
    return 0;
}

P1433 吃奶酪

原文：https://www.cnblogs.com/FUXyao/p/12885233.html