题目：宝藏
思路：
安利某大佬的博客，代码超好看！
这题有点卡常，要注意常数优化。
思路就是状压+搜索。
先枚举一个起点。
令 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 1e9int 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;
}