答案与解析
正确答案:<p style="text-align: left;">#include<bits/stdc++.h></p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">typedef long long ll;</p><p style="text-align: left;">int n,m,tot,ans;</p><p style="text-align: left;">int mapp[110][110],dis[110][110],Log[4100];</p><p style="text-align: left;">int f[15][4100],g[4100],ref[4100],v[15],p[15];</p><p style="text-align: left;">int main(){</p><p style="text-align: left;"> //freopen("treasure.in","r",stdin);</p><p style="text-align: left;"> //freopen("treasure.out","w",stdout);</p><p style="text-align: left;"> scanf("%d%d",&n,&m);</p><p style="text-align: left;"> register int i,j,a,b,c,x;</p><p style="text-align: left;"> for(i=0;i<n;i++) for(j=0;j<n;j++) mapp[i][j]=60000000;</p><p style="text-align: left;"> for(i=1;i<=m;i++){</p><p style="text-align: left;"> scanf("%d%d%d",&a,&b,&c),a--,b--;</p><p style="text-align: left;"> mapp[a][b]=mapp[b][a]=min(mapp[a][b],c);</p><p style="text-align: left;"> }//建图</p><p style="text-align: left;"> for(i=0;i<n;i++) Log[1<<i]=i;</p><p style="text-align: left;"> memset(f,0x3f,sizeof(f));</p><p style="text-align: left;"> for(i=0;i<n;i++) f[0][1<<i]=0;</p><p style="text-align: left;"> for(i=0;i<n;i++) //开始DP</p><p style="text-align: left;"> for(x=0;x<(1<<n);x++){</p><p style="text-align: left;"> tot=0;</p><p style="text-align: left;"> for(a=0;a<n;a++) </p><p style="text-align: left;"> if(!(x&(1<<a))){</p><p style="text-align: left;"> v[tot]=60000000,p[tot]=1<<a;</p><p style="text-align: left;"> for(j=x;j;j-=j&-j){</p><p style="text-align: left;"> b=Log[j&-j];</p><p style="text-align: left;"> v[tot]=min(v[tot],mapp[a][b]*(i+1));//计算代价</p><p style="text-align: left;"> }</p><p style="text-align: left;"> tot++;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> for(j=1;j<(1<<tot);j++){</p><p style="text-align: left;"> g[j]=g[j-(j&-j)]+v[Log[j&-j]];//每个点与x中的某个点连通所需要的最小代价。 </p><p style="text-align: left;"> ref[j]=ref[j-(j&-j)]|p[Log[j&-j]];//枚举子集</p><p style="text-align: left;"> f[i+1][x|ref[j]]=min(f[i+1][x|ref[j]],f[i][x]+g[j]);</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;"> ans=1<<30;</p><p style="text-align: left;"> for(i=0;i<=n;i++) ans=min(ans,f[i][(1<<n)-1]);//最优状态从走到每一个点但最深深度不同的状态中取</p><p style="text-align: left;"> printf("%d",ans);</p><p style="text-align: left;"> return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。