[DFS] [洛谷] P1433 吃奶酪
程序员文章站
2024-01-11 15:20:04
...
该题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;
}