http://www.luogu.org/problem/show?pid=1433
直接DFS即可，有一个剪枝
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define ms(i,j) memset(i,j, sizeof i); using namespace std; struct pos { double x; double y; }p[30]; int n; double dist(pos a, pos b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double ans = 10000000; int visit[30]; int dfs(int x, double l, int a) { if (l>ans) return 0;//剪枝 if (a==n) {if (ans>l) ans = l; return 0;} for (int i=1;i<=n;i++) { if (!visit[i]) { visit[i] = true; dfs(i, l+dist(p[x], p[i]), a+1); visit[i] = false; } } } int main() { scanf("%d", &n); p[0].x = 0, p[0].y = 0; for (int i=1;i<=n;i++) scanf("%lf%lf", &p[i].x, &p[i].y); ms(visit, false);visit[0] = true; dfs(0,0,0); printf("%.2lf", ans); return 0; }