6. 线型网络

★★☆ 输入文件：linec.in 输出文件：linec.out 简单对比
时间限制：1 s 内存限制：256 MB

【问题描述】

有 N(N<=20)台 PC 放在机房内，现在要求由你选定一台 PC，用共N−1条网线从这台机器开始一台接一台地依次连接他们，最后接到哪个以及连接的顺序也是由你选定的，为了节省材料，网线都拉直。求最少需要一次性购买多长的网线。(说白了,就是找出 N 的一个排列 P1P2P3..PN 然后 P1−>P2−>P3−>...−>PN 找出 |P1P2|+|P2P3|+...+|PN−1PN| 长度的最小值)

【输入格式】

第一行 N ，下面 N 行，每行分别为机器的坐标(x,y)(x为实数−100<=x,y<=100)

【输出格式】

最小的长度，保留两位小数。

【输入样例】

3
0 0
1 1
1 -1

【输出样例】

2.83

/*

    ans[sta][i]点的集合为sta，且最后一个点是i的最短路

*/

#include<cmath>

#include<cstdio>

#include<iostream>

using namespace std;

int n,num1[<<];

double x[],y[],dis[][],ans[<<][];

int main(){

    //freopen("Cola.txt","r",stdin);

    freopen("linec.in","r",stdin);freopen("linec.out","w",stdout);

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++){

            if(i==j)continue;

            dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

        }

    for(int i=;i<=n;i++)num1[<<i]=i+;

    for(int i=;i<(<<n);i++){

        if(!num1[i]){

            for(int j=i;j;j-=j&-j){

                ans[i][num1[j&-j]]=0x3f3f3f3f;

                for(int k=i-(j&-j);k;k-=(k&-k))

                    if (ans[i][num1[j&-j]]>ans[i-(j&-j)][num1[k&(-k)]]+dis[num1[j&-j]][num1[k&-k]])

                        ans[i][num1[j&-j]]=ans[i-(j&-j)][num1[k&(-k)]]+dis[num1[j&-j]][num1[k&-k]];

            }

        }

    }

    double Ans=0x7fffffff;

    for(int i=;i<=n;i++)Ans=min(Ans,ans[(<<n)-][i]);

    printf("%.2lf",Ans);

}