当初考场上没有想到如何保存状态，写了个的，拿了70分
dp 数组记录最大深度d ，和已选点状态s
对于每个s ，枚举补集进行更新
枚举补集复杂度为，总复杂度1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using namespace std;
const int N=14,INF=1<<30;
int n,m,dp[N][1<<N],w[1<<N],idx[1<<N],pos[1<<N],c[N],f[N][N],val[N];
vector<int> e[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) f[i][j]=INF;
for(int d=0;d<=n;d++)
for(int i=0;i<(1<<n);i++) dp[d][i]=INF;
for(int i=1;i<=m;i++)
{
int u,v,val;
scanf("%d%d%d",&u,&v,&val);
f[u][v]=f[v][u]=min(val,f[u][v]);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if (f[i][j]!=INF) e[i].push_back(j);
for(int i=1;i<=n;i++) dp[0][1<<(i-1)]=0;
for(int d=0;d<=n;d++)
for(int s=0,cnt=0;s<(1<<n);s++,cnt=0) if (dp[d][s]!=INF)
{
for(int i=1;i<=n;i++)
if (!(s>>(i-1)&1)) pos[1<<cnt]=i,val[i]=INF,c[cnt++]=i;
for(int k=1;k<(1<<cnt);k++)
{
int x=0;
for(int i=0;i<cnt;i++)
if ((k>>i)&1) x|=1<<(c[i]-1);
idx[k]=x,w[x]=INF;
}
for(int i=1;i<=n;i++) if ((s>>(i-1))&1)
for(int j=0;j<e[i].size();j++)
{
int to=e[i][j];
if (!((s>>(to-1))&1)) val[to]=min(f[i][to],val[to]);
}
for(int k=1;k<(1<<cnt);k++)
if (w[idx[k-(k&-k)]]!=INF&&val[pos[k&-k]]!=INF)
w[idx[k]]=w[idx[k-(k&-k)]]+(d+1)*val[pos[k&-k]];
for(int k=0;k<(1<<cnt);k++)
if (!(s&idx[k])&&w[idx[k]]!=INF)
dp[d+1][s|idx[k]]=min(dp[d+1][s|idx[k]],dp[d][s]+w[idx[k]]);
}
int ans=INF;
for(int i=1;i<=n;i++)
ans=min(ans,dp[i][(1<<n)-1]);
printf("%d",ans);
return 0;
}