uva 216 Getting in Line 最短路，全排列暴力做法

题目给出离散的点，要求求出一笔把所有点都连上的最短路径。

最多才8个点，果断用暴力求。

用next_permutation举出全排列，计算出路程，记录最短路径。

这题也可以用dfs回溯暴力，但是用最小生成树要小心一点，最小生成树求的是最小连通图，而不是连成一条，不能用Kruscal，Prim算法修改一下也可以使用，改成选点时仅考虑头尾两点即可。

代码：

include    
#include    
#include    
#include    
using namespace std;  
  
const int maxn = 10;  
  
int p[maxn], rec[maxn], n;  
double sum, x[maxn], y[maxn];  
  
double dis(double ax, double ay, double bx, double by) {  
    double dx, dy;  
    dx = ax - bx;  
    dy = ay - by;  
    return sqrt(dx * dx + dy * dy) + 16;  
}  
  
void solve(void) {  
    double tmp = 0;  
    for (int i = 0; i < n - 1; i++)  
        tmp += dis(x[p[i]], y[p[i]], x[p[i + 1]], y[p[i + 1]]);  
    if (tmp < sum) {  
        sum = tmp;  
        for (int i = 0; i < n; i++)  
            rec[i] = p[i];  
    }  
}  
  
int main() {  
    int cnt = 0;  
    while (scanf("%d", &n) && n) {  
        for (int i = 0; i < n; i++) {  
            scanf("%lf%lf", &x[i], &y[i]);  
            p[i] = i;  
        }  
        sum = 0xffffff;  
        do {  
            solve();  
        } while (next_permutation(p, p + n));  
        printf("**********************************************************\n");  
        printf("Network #%d\n", ++cnt);  
        for (int i = 0; i < n - 1; i++)  
            printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet.\n", int(x[rec[i]]), int(y[rec[i]]), int(x[rec[i + 1]]), int(y[rec[i + 1]]), dis(x[rec[i]], y[rec[i]], x[rec[i + 1]], y[rec[i + 1]]));  
        printf("Number of feet of cable required is %.2lf.\n", sum);  
    }  
    return 0;  
}  

#include 
#include 
#include 
#include 
using namespace std;

const int maxn = 10;

int p[maxn], rec[maxn], n;
double sum, x[maxn], y[maxn];

double dis(double ax, double ay, double bx, double by) {
	double dx, dy;
	dx = ax - bx;
	dy = ay - by;
	return sqrt(dx * dx + dy * dy) + 16;
}

void solve(void) {
	double tmp = 0;
	for (int i = 0; i < n - 1; i++)
		tmp += dis(x[p[i]], y[p[i]], x[p[i + 1]], y[p[i + 1]]);
	if (tmp < sum) {
		sum = tmp;
		for (int i = 0; i < n; i++)
			rec[i] = p[i];
	}
}

int main() {
	int cnt = 0;
	while (scanf("%d", &n) && n) {
		for (int i = 0; i < n; i++) {
			scanf("%lf%lf", &x[i], &y[i]);
			p[i] = i;
		}
		sum = 0xffffff;
		do {
			solve();
		} while (next_permutation(p, p + n));
		printf("**********************************************************\n");
		printf("Network #%d\n", ++cnt);
		for (int i = 0; i < n - 1; i++)
			printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet.\n", int(x[rec[i]]), int(y[rec[i]]), int(x[rec[i + 1]]), int(y[rec[i + 1]]), dis(x[rec[i]], y[rec[i]], x[rec[i + 1]], y[rec[i + 1]]));
		printf("Number of feet of cable required is %.2lf.\n", sum);
	}
	return 0;
}