洛谷P1433 吃奶酪【dfs】【剪枝】

题目：https://www.luogu.org/problemnew/show/P1433

题意：

给定n个坐标，要求从（0，0）开始走遍所有点，最少经过的路程。

思路：

刚开始想像数字三角形一样适用next_permutation，枚举坐标的顺序，一旦出现距离比当前最优解要差时就sort剪枝。

这里sort的起始和结束要注意一下，和那道题不一样。开始应该是i+1

但是还是有一个点会TLE。毕竟sort了一下还是会慢一点...?

所以还是老老实实dfs吧。道理都是一样的，搜索走的下标排列，一旦出现比最优解差就直接回溯。

 #include<stdio.h>

 #include<stdlib.h>

 #include<map>

 #include<set>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #include<queue>

 #define inf 0x7f7f7f7f

 using namespace std;

 typedef long long LL;

 typedef pair<int, int> pr;

 int n;

 struct node{

     double x, y;

 }pos[];

 int per[];

 double d[][];

 double dist(node a, node b)

 {

     return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));

 }

 bool cmp(int a, int b)

 {

     return a > b;

 }

 bool vis[];

 double ans = inf;

 void dfs(int pre, int m, double res)

 {

     if(res > ans)return;

     if(m == n){

         ans = min(ans, res);

         return;

     }

     for(int i = ; i <= n; i++){

         if(!vis[i]){

             vis[i] = true;

             dfs(i, m + , res + d[pre][i]);

             vis[i] = false;

         }

     }

     return;

 }

 int main()

 {

     scanf("%d", &n);

     pos[].x = ;

     pos[].y = ;

 //    node st;

 //    st.x = 0;st.y = 0;

     for(int i = ; i <= n; i++){

         scanf("%lf%lf", &pos[i].x, &pos[i].y);

         per[i] = i;

     }

     for(int i = ; i <= n; i++){

         for(int j = i + ; j <= n; j++){

             d[i][j] = d[j][i] = dist(pos[i], pos[j]);

         }

     }

     dfs(, , );

 //    double ans = inf;

 //    do{

 //        double tmp = 0;

 //        //double tmp = dist(st, pos[per[1]]);

 //        for(int i = 1; i < n; i++){

 //            tmp += d[per[i]][per[i + 1]];

 //            //tmp += dist(pos[per[i]], pos[per[i + 1]]);

 //            if(tmp > ans){

 //                sort(per + i + 1, per + 1 + n, cmp);

 //                break;

 //            }

 //        }

 ////        for(int i = 1; i <= n; i++){

 ////                cout<<per[i]<<" ";

 ////            }

 ////            cout<<endl;

 ////        if(tmp < ans){

 ////

 ////        }

 //        //tmp += dist(st, pos[per[1]]);

 //        tmp += d[0][per[1]];

 //        ans = min(ans, tmp);

 //    }while(next_permutation(per + 1, per + 1 + n));

     printf("%.2lf\n", ans);

     return ;

 }