欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[DFS] [洛谷] P1433 吃奶酪

程序员文章站 2024-01-11 15:20:04
...

[DFS] [洛谷] P1433 吃奶酪

该题DFS的过程没有任何乐趣

甚至打完都处于

AC了?可是为什么AC呢?的状态

 

这道题的重点 难点在于提前枚举所有点之间的距离

有了该操作

(也是我没有想到的操作)

才使得搜索过程成为可能

既然可以搜索

那么一发AC是非常容易的

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

typedef long long ll;

const int MAXN = 1e3 + 10;

double point[MAXN][2] = {0};

double dist[MAXN][MAXN] = {0};

bool used[MAXN] = {1};

double ans = 1e9 + 10, len;

void dfs(int rit, double sum, int num)
{
    if(sum > ans)
        return;
    
    if(num == len)
    {
        ans = min(ans, sum);
    }
    
    for(int i = 1; i <= len; i++)
    {
        if(!used[i])
        {
            used[i] = 1;
            
            dfs(i, sum + dist[rit][i], num + 1);
            
            used[i] = 0;
        }
    }
}

int main()
{
    cin>>len;

    point[0][0] = 0;

    point[0][1] = 0;

    for(int i = 1; i <= len; i++)
    {
        cin>>point[i][0]>>point[i][1];
    }
    //       x            y
    // 1 point[i][0] point[i][1]
    // 2 point[j][0] (point[i][1] - point[j][1])
    

    for(int i = 0; i <= len; i++)
    {
        for(int j = 0; j <= len; j++)
        {
            dist[i][j] = sqrt( (point[i][0] - point[j][0]) * (point[i][0] - point[j][0]) + (point[i][1] - point[j][1]) * (point[i][1] - point[j][1]));
        }
    }

    /*for(int i = 0; i <= len; i++)
    {
        for(int j = 0; j <= len; j++)
        {
            cout<<fixed<<setprecision(2)<<dist[i][j]<<' ';
        }
        cout<<endl;
    }*/

    dfs(0, 0, 0);

    cout<<fixed<<setprecision(2)<<ans<<endl;
    
    return 0;
}

 

相关标签: P1433 吃奶酪