题目：宝藏
思路： 安利某大佬的博客，代码超好看！ 这题有点卡常，要注意常数优化。 思路就是状压+搜索。 先枚举一个起点。 令 dp[st] 表示状态为st的时候的最小代价，状态指的是每个点是否和起点连通的二进制状压表示。 再令 d[i] 表示 i 到起点的距离。 假设当前状态为st，那么枚举st中的一个点i，和st补集中的一个点j，如果这两个点直接连通，就可以进行转移。 转移方程：
dp[st|y]=min(dp[st|y],dp[st]+a[i][j]*(d[i]+1)) //这里的 '|' 表示异或而非条件可以简单的加上一个最优化剪枝，卡过 -> 不那么惊险的卡过。
代码：
#include<bits/stdc++.h> using namespace std; #define maxn 12 #define read(x) scanf("%d",&x) #define inf 1e9 int n,m; int a[maxn+5][maxn+5]; int ans=inf; int d[maxn+5],dp[(1<<maxn)+5]; void dfs(int st) { if(dp[st]>=ans) return ; for(int i=1;i<=n;i++) { int x=(1<<i-1); if(!(st&x)) continue; for(int j=1;j<=n;j++) { int y=(1<<j-1); if(st&y) continue; if(a[i][j]==inf) continue; if(dp[st|y]>dp[st]+a[i][j]*(d[i]+1)) { dp[st|y]=dp[st]+a[i][j]*(d[i]+1); d[j]=d[i]+1; dfs(st|y); } } } } int main() { read(n),read(m); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=inf; for(int i=1;i<=m;i++) { int x,y,z; read(x),read(y),read(z); a[x][y]=a[y][x]=min(a[x][y],z); } for(int i=1;i<=n;i++) { for(int j=1;j<(1<<n);j++) dp[j]=inf; dp[(1<<i-1)]=0; memset(d,0,sizeof(d)); dfs((1<<i-1)); ans=min(ans,dp[(1<<n)-1]); } printf("%d",ans); return 0; }