Description：

一张图上选一个点为起点，某条边的代价是边权 $\times$ 起点到边的起点的距离，最小化代价使得所有点都联通。

$1\le n \le 12$

Solution：

$n\le 12$ 想到状压 $DP$ ，设 $f[S][i]$ 表示当前状态为 $S$ ，最外层深度为 $i$ 的最小代价，每次枚举新的外层的点和深度转移，但是有个问题，就是新的外层的点不一定和原来最外层的点相连，但是可以发现这样跳过一些层一定不是最优解，所以不用考虑这样转移的合法性。有两个优化，一是预处理每个状态可能扩展到的最外层的点的集合，转移时枚举这个集合的子集即可，二是预处理每个状态到可扩展出的点的最短距离，转移时直接加上即可，深度不同但转移相同的可以直接同时转移，复杂度 $O(3^nn)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 13

int f[1 << 12][MAXN];

#define MAXM 1010

struct edge

{

    int to,nxt,w;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

int g[MAXN][MAXN];

inline void add(int a,int b,int c)

{

    g[a][b] = g[b][a] = c;

    ++edgenum;e[edgenum].to = b;e[edgenum].w = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    ++edgenum;e[edgenum].to = a;e[edgenum].w = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

    return;

}

int expand[1 << 12],val[1 << 12][MAXN];

inline int read()

{

    register int res = 0;

    register char c = getchar();

    while(!isdigit(c))c = getchar();

    while(isdigit(c))

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res;

}

int main()

{

    scanf("%d%d",&n,&m);

    register int a,b,c;

    for(register int i = 1;i <= m;++i)

    {

        a = read();b = read();c = read();

        --a;--b;

        add(a,b,c);

    }

    memset(expand,0,sizeof(expand));

    memset(val,0x3f,sizeof(val));

    register int tot = (1 << n) - 1;

    for(register int b = 0;b <= tot;++b)

    {

        for(register int k = 0;k < n;++k)

        {

            if((b & (1 << k)) == 0)continue;

            for(register int i = lin[k];i != 0;i = e[i].nxt)

            {

                if(b & (1 << e[i].to))continue;

                expand[b] |= (1 << e[i].to);

                val[b][e[i].to] = min(val[b][e[i].to],e[i].w);

            }

        }

    }

    memset(f,0x3f,sizeof(f));

    for(register int k = 0;k < n;++k)f[1 << k][1] = 0;

    for(register int b = 1;b <= tot;++b)

    {

        for(register int s = expand[b];s != 0;s = (s - 1) & expand[b])

        {

            register int sum = 0;

            for(register int k = 0;k < n;++k)

                if(s & (1 << k))

                    sum += val[b][k];

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

                f[b | s][i + 1] = min(f[b | s][i + 1],f[b][i] + sum * i);

        }

    }

    register int ans = 0x3f3f3f3f;

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

    {

        ans = min(ans,f[tot][i]);

    }

    printf("%d\n",ans);

    return 0;

}