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

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

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

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

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

代码：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
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;
}