Luogu

分析

状压 DP 。

设 $f_{S,i}$ 表示已经选了 $S$ ，最远距离为 $i$ 的最小代价。

转移枚举一个子集 $T$ ，然后由 $f_{T,i-1}+cost$ 转移到 $f_{S,i}$ 即可。

注意到这里的 $T$ 要能够扩展到 $S$ ，可以预处理出一个 $g_S$ 表示 $S$ 能扩展到的集合来快速判断。

$cost$ 直接对于每个不在 $T$ 中的元素找一个最近的 $T$ 中的点就好了。

边界是 $f_{\{i\},i}=0$ ，答案是 $\min\left\{f_{U,i}\right\}$

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=12+10;
const int inf=0x3f3f3f3f;

int n,m,U;
int G[N][N];
int f[1<<12][N],g[1<<12];

int main() {
    n=read(),m=read(),U=1<<n;
    
    memset(G,0x3f,sizeof(G));
    for (re int i=0;i<n;++i) G[i][i]=0;
    for (re int i=1;i<=m;++i) {
        int u=read()-1,v=read()-1,w=read();
        G[u][v]=G[v][u]=min(G[u][v],w);
    }

    for (re int S=1;S<U;++S)
        for (re int i=0;i<n;++i) {
            if (!(S&(1<<i))) continue;
            for (re int j=0;j<n;++j)
                if (G[i][j]!=inf) g[S]|=1<<j;
        }
    
    memset(f,0x3f,sizeof(f));
    for (re int i=0;i<n;++i) f[1<<i][0]=0;
    for (re int S=2;S<U;++S)
        for (re int T=S&(S-1);T;T=(T-1)&S) {
            if ((g[T]|S)!=g[T]) continue;
            int SS=S-T,now=0;
            for (re int i=0;i<n;++i) {
                if (!(SS&(1<<i))) continue;
                int mn=inf;
                for (re int j=0;j<n;++j) {
                    if (!(T&(1<<j))) continue;
                    mn=min(mn,G[j][i]);
                }
                now+=mn;
            }
            for (re int i=1;i<n;++i) {
                if (f[T][i-1]==inf) continue;
                f[S][i]=min(f[S][i],f[T][i-1]+now*i);
            }
        }
    
    int ans=inf;
    for (re int i=0;i<n;++i) ans=min(ans,f[U-1][i]);
    printf("%d\n",ans);
    return 0;
}