按层dp，f[i][j]表示已扩展i子集的节点当前在第j层的最小代价，预处理点集间距离即可。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 12 #define inf 1000000000 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,m,a[N][N],f[1<<N][N],dis[1<<N][1<<N]; int main() { n=read(),m=read(); memset(a,42,sizeof(a)); for (int i=1;i<=m;i++) { int x=read()-1,y=read()-1,z=read(); a[x][y]=min(a[x][y],z),a[y][x]=min(a[y][x],z); } memset(dis,42,sizeof(dis)); for (int i=1;i<(1<<n);i++) if ((i&-i)<i) { for (int j=0;j<n;j++) if (i&(1<<j)) for (int k=0;k<n;k++) if ((i&(1<<k))&&j!=k) dis[i][1<<j]=min(dis[i][1<<j],a[j][k]); for (int j=i;j;j=j-1&i) if ((j&-j)<j) dis[i][j]=min(dis[i^j^(j&-j)][j&-j]+dis[i^(j&-j)][j^(j&-j)],inf); } memset(f,42,sizeof(f)); for (int i=0;i<n;i++) f[1<<i][1]=0; for (int k=2;k<=n;k++) for (int i=1;i<(1<<n);i++) for (int j=i;j;j=j-1&i) if (dis[i][j]<100000000) f[i][k]=min(f[i][k],f[i^j][k-1]+dis[i][j]*(k-1)); int ans=inf; for (int i=1;i<=n;i++) ans=min(ans,f[(1<<n)-1][i]); cout<<ans; return 0; }