Aimee

显然的状压dp，但是还要考虑根节点。

那么把根节点也扔进去$f_{i,j}$表示i状态，有j层高。

转移的时候需要枚举i的子集，怎样保证子集合法？
可以预处理一个数组表示i状态最多可以扩展一次扩展成什么，来解决。

处理新增的部分的时候·，我们假定所有新点到根节点的距离都是我们当前枚举的k，这样，一方面如果我们枚举的子集不符合这个层数恰好为k，那么肯定算出来的值偏大（$*$的大了），另一方面所有符合这一条的集合一定会被枚举。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
int n,m;
int x,y,z;
const int maxn=1<<15;
int g[maxn];
int f[maxn][50];
int inf;
int dis[20][20];
signed main(){
    scanf("%d%d",&n,&m);
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&x,&y,&z);
        x--;
        y--;
        dis[x][y]=dis[y][x]=min(z,dis[x][y]);
    }
    memset(f,0x3f,sizeof(f));
    inf=f[0][0];
    int lim=(1<<n)-1;
    for(int i=1;i<=lim;++i){
        for(int j=0;j<n;++j){
            if(((1<<j)|i)==i){
                dis[j][j]=0;
                for(int k=0;k<n;++k){
                    if(dis[j][k]!=inf){
                        g[i]|=(1<<k);
                    }
                }
            }
        }
    }
    for(int i=0;i<n;++i){
        f[1<<i][0]=0;
    }
    for(int i=2;i<=lim;++i){
        for(int j=i-1;j;j=(j-1)&i){
            if((g[j]|i)==g[j]){
                int sum=0;
                int k=j^i;
                for(int x=0;x<n;++x){
                    if((1<<x)&k){
                        int tem=inf;
                        for(int y=0;y<n;++y){
                            if((1<<y)&j){
                                tem=min(tem,dis[x][y]);
                            }
                        }
                        sum+=tem;
                    }
                }
                for(int x=1;x<n;++x){
                    if(f[j][x-1]!=inf){
                        f[i][x]=min(f[i][x],f[j][x-1]+sum*x);
                    }
                }
            }
        }
    }
    for(int i=0;i<n;++i){
        f[lim][1]=min(f[lim][1],f[lim][i]);
    }
    cout<<f[lim][1];
    return 0;
}