【dfs】P1433 吃奶酪

佚名 6年前 (2019-04-22) 随笔 631人围观抢沙发百度已收录

题目描述

房间里放着n块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在(0,0)点处。

输入输出格式

输入格式：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

第一行一个数n (n<=15)

接下来每行2个实数，表示第i块奶酪的坐标。

两点之间的距离公式=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))

输出格式：

一个数，表示要跑的最少距离，保留2位小数。

输入输出样例

输入样例：

输出样例：

7.41

[思路]：dfs+剪枝

这里用的剪枝是最优性剪枝，顾名思义就是如果当前的距离都大于你记录的最小距离了，你搜也没意思了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
const int maxn=999999999;
const int minn=-999999999;
inline int read() {
    char c = getchar();
    int x = 0, f = 1;
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n,v[1001];
double x[100];
double y[20];
double dis[1001][1001];
double ans=1231234424.0;
void dfs(int done/*×ß¹ý¶àÉÙµã*/,int now/*ÏÖÔÚµÄµã*/,double tot/*¾àÀë*/ ) {
    if(tot>ans) { //Ð¡Ð¡µÄ¼ôÖ¦£¬×îÓÅÐÔ¼ôÖ¦
        return ;
    }
    if(done==n) {
        if(tot<ans) {
            ans=tot;
        }
        return ;
    }
    for(int i=1; i<=n; ++i) {
        if(!v[i]) {
            v[i]=1;  
            dfs(done+1,i,tot+dis[now][i]); 
            v[i]=0;  //»ØËÝ 
        }
    }
}
int main() {
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>x[i]>>y[i];
    x[0]=0;
    y[0]=0;
    for(int i=0; i<=n; i++)
        for(int j=0; j<=n; j++)
            dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    dfs(0,0,0.0);
    printf("%.2f",ans);
    return 0;
}