1993.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1993 on 2006-08-11 at 16:32:30 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
 
const int N = 8, S = 1 << N;
const double INF = 1e20;
 
class Point {
public:
	int x, y;
	void make() { scanf("%d %d", &x, &y); }
	double dis(const Point& p) const { return sqrt(1.0*(x-p.x)*(x-p.x)+(y-p.y)*(y-p.y)); }
};
 
int main()
{
	Point p[N+2];
	double path[S][N];
	int t, T, i, j, k;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		for(i = 0; i < N+2; i++) p[i].make();
		for(i = 1; i < S; i++)
			for(j = 0; j < N; j++)
				if(i == (1<<j)) path[i][j] = p[1].dis(p[j+2]);
				else if(i&(1<<j)) {
					path[i][j] = INF;
					int st = i ^ (1 << j);
					for(k = 0; k < N; k++)
						if(st&(1<<k)) path[i][j] = min(path[i][j], path[st][k]+p[j+2].dis(p[k+2]));
				}
		double best = INF;
		for(i = 0; i < N; i++) best = min(best, path[S-1][i]+p[0].dis(p[i+2]));
		printf("%.3lf\n", best+p[0].dis(p[1]));
	}
	
	return 0;
}