【状压DP】十二桥问题（nowcoder 1104-B）

nowcoder 1104-B

给你一张无向图，问你从1开始经过几个必要的边，然后回到1的最短路径

因为关键边很少，先从每个关键点跑一遍dij，得到最短的距离

设 f s , i f_{s,i} fs,i表示必要边的状态为s，目前第一个关键点的最短距离，然后直接转移

#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 50010 #define M 200021 #define mp make_pair #define fs first #define sn second using namespace std; ll n,m,k,x,y,z,w,tot,ans,p[N],b[N],h[N],q[/span>30],to[30][30],f[50000][30]; priority_queue<pair<ll,ll> >d; struct rec { 
          ll l,to,nx; }e[M<<1]; struct node { 
          node(ll xx=0,ll yy=0,ll zz=0) { 
          x=xx,y=yy,z=zz; } ll x,y,z; }a[30]; void add(ll x,ll y,ll z) { 
          e[++tot].to=y; e[tot].l=z; e[tot].nx=h[x]; h[x]=tot; return; } void dij(ll x) { 
          memset(b,127/3,sizeof(b)); memset(p,0,sizeof(p)); b[x]=0; d.push(mp(0,x)); while(!d.empty()){ 
          ll u=d.top().sn; d.pop(); if(p[u])continue; p[u]=1; for(ll i=h[u];i;i=e[i].nx){ 
          ll v=e[i].to; if(b[u]+e[i].l<b[v]){ 
          b[v]=b[u]+e[i].l; d.push(mp(-b[v],v)); } } } return; } int main() { 
          scanf("%lld%lld%lld",&n,&m,&k); for(ll i=1;i<=m;++i){ 
          scanf("%lld%lld%lld",&x,&y,&z); if(i<=k){ 
          a[i]=node(x,y,z); q[++w]=x; q[++w]=y; } add(x,y,z); add(y,x,z); } q[++w]=1; sort(q+1,q+1+w); w=unique(q+1,q+1+w)-q-1; for(ll i=1;i<=w;++i){ 
          dij(q[i]);//跑最短路 for(ll j=1;j<=w;++j) to[i][j]=b[q[j]]; } for(ll i=1;i<=k;++i){ 
          a[i].x=lower_bound(q+1,q+1+w,a[i].x)-q; a[i].y=lower_bound(q+1,q+1+w,a[i].y)-q; } memset(f,127/3,sizeof(f)); f[0][1]=0; for(ll s=0;s<(1<<k)-1;++s) for(ll i=1;i<=k;++i) if(!(s&(1<<i-1))) for(ll j=1;j<=w;++j){ 
          f[s|(1<<i-1)][a[i].x]=min(f[s|(1<<i-1)][a[i].x],f[s][j]+min(to[j][a[i].y]+a[i].z,to[j][a[i].x]+a[i].z+to[a[i].y][a[i].x]));//有两种走的方法 f[s|(1<<i-1)][a[i].y]=min(f[s|(1<<i-1)][a[i].y],f[s][j]+min(to[j][a[i].x]+a[i].z,to[j][a[i].y]+a[i].z+to[a[i].x][a[i].y])); } ans=1e15; for(ll i=1;i<=w;++i) ans=min(ans,f[(1<<k)-1][i]+to[i][1]); printf("%lld",ans); return 0; }