传送门

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

// 状压DP类比二进制枚举
// 从已有的状态更新至为更新的状态
// 比如 {1, 1, 0, 0} 表示已经走了1, 2, 剩下3, 4未走
// {1, 1, 0, 0} -> {1, 1, 1, 0} // 表示从走了1, 2 更新到走了 1, 2, 3
// {1, 1, 0, 0} -> {1, 1, 0, 1} // 表示从走了1, 2 更新到走了 1, 2, 4


// 板子
// f(i)表示在i状态下的代价(max, min, cnt ...)
// f(i, j) 表示处在第j个节点的i状态下的代价，其中需要满足((i >> j) & 1) == true，因为j节点必须选才可以保证在第j个节点

// 一般情况下先枚举状态，之后枚举节点j，然后枚举从哪个节点k更新过来（被更新的节点之前一定未被选即f(i, j) = {f{i - (1 << j), k} + work(...);}
// 最终状态一般一般一般（强调三遍）从全选的状态中拿到最终结果，记f{(1 << n) - 1, k}

const int N = 18;
double f[1 << N][N];

int n;

struct eg
{
        double x, y, z, w;
} e[N];

double s[N][N];
double w[N][N];

double get_s(eg a, eg b)
{
        return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));
}

int main()
{
        ios::sync_with_stdio(false), cin.tie(0);

        cin >> n;

        for (int i = 0; i < n; i ++) cin >> e[i].x >> e[i].y >> e[i].z >> e[i].w;

        for (int i = 0; i < n; i ++)
                for (int j = 0; j < n; j ++)
                        s[i][j] = get_s(e[i], e[j]);

        for (int i = 0; i < n; i ++)
                for (int j = 0; j < n; j ++)
                        w[i][j] = s[i][j] * e[j].w;

        for (int i = 0; i < 1 << n; i ++) 
                for (int j = 0; j < n; j ++)
                        f[i][j] = 1e18 + 10; // 一定不能用memset();


        //下面是状压板子
        for (int i = 0; i < n; i ++) f[1 << i][i] = 0; //初始化先更新

        for (int i = 0; i < 1 << n; i ++)
                for (int j = 0; j < n; j ++)
                        if ((i >> j) & 1)  //更新j点所以状态中一定要有j
                                for (int k = 0; k < n; k ++)
                                                if ((i >> k) & 1)  //由k转移过来，所以状态中要有k
                                                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]); // 肯定由不含j的状态转移过来，这是毋庸置疑的

        double ans = 1e18 + 10;
        for (int i = 0; i < n; i ++) 
                ans = min(ans, f[(1 << n) - 1][i]); //扫描以i为终点的全部走过的状态

        printf("%.2lf\n", ans);

        return 0;
}