题解 P3959 【宝藏】（状压）

n出的那么小，显然就是让我们来状压的。 f[i]表示选的点状态为i时的最小代价，dis[i]表示到i这个这条路已经选了多少个点了。转移类似于spfa，如果走过来的代价要小的话：$f[u|(1<<(j-1))]=f[u]+dis[i]*val(i\to j)$ 然后，实现起来就用大法师就行了。打其实很好打，就看想不想的到了 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m; int g[20][20],f[20000],dis[20]; int dfs(int u) { for(int i=1;i<=n;i++) if((1<<(i-1))&u)//枚举从那个点继续往下打 { for(int j=1;j<=n;j++) if(!((1<<(j-1))&u) && g[i][j]!=-1)//枚举要到的点 { if(f[u|(1<<(j-1))]>f[u]+dis[i]*g[i][j]) { int tmp=dis[j]; dis[j]=dis[i]+1; f[u|(1<<(j-1))]=f[u]+dis[i]*g[i][j]; dfs(u|(1<<(j-1))); dis[j]=tmp;//注意要还原 } } } } int main() { memset(g,-1,sizeof(g)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); if(g[x][y]==-1) g[x][y]=z,g[y][x]=z; g[x][y]=min(g[x][y],z); g[y][x]=min(g[y][x],z); } int ans=0x7ffffff; for(int i=1;i<=n;i++)//枚举第一个打通的起点 { memset(f,0x7f,sizeof(f)); memset(dis,0x7f,sizeof(dis)); dis[i]=1,f[1<<(i-1)]=0; dfs(1<<(i-1)); ans=min(ans,f[(1<<n)-1]); } printf("%d",ans); return 0; } ```