题目：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 ;
}