SSL-ZYC 洛谷 P1433 吃奶酪

本文主要是介绍SSL-ZYC 洛谷 P1433 吃奶酪，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

---

思路:
明显的DFS！
这道题的思路是十分清晰的：
1.读入，顺便用勾股定理求两点之间的距离。
2.DFS，从（0，0）开始，搜索每一个点，将最短答案记录在minn里。
EASY!

---

代码：

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;double a[101][101],x[101],y[101],minn;
int n,t[101];void dfs(int x,int y,double k)  //DFS
{if (y==n)  //已经把所有点走完{if (k<minn) minn=k;  //记录最短答案return;}if (k>=minn) return;  //剪枝for (int i=1;i<=n+1;i++)  //枚举一个点（加上(0,0)共有n+1个点）if (t[i]==0)  //没有走过{t[i]=1;dfs(i,y+1,k+a[x][i]);t[i]=0;} 
}int main()
{scanf("%d",&n);x[1]=0;y[1]=0;for (int i=2;i<=n+1;i++){cin>>x[i]>>y[i];for (int j=1;j<i;j++)a[i][j]=a[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));   //求距离} t[1]=1;minn=2147483647;dfs(1,0,0);printf("%0.2lf\n",minn);return 0;
} 

这篇关于SSL-ZYC 洛谷 P1433 吃奶酪的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---