【bzoj5180】[Baltic2016]Cities 斯坦纳树

这题一看显然是一个裸的斯坦纳树

我们用$f[i][j]$表示经过的路径中包含了状态$i$所表示的点，且连接了$j$号点的最短路径。

显然，$f[i][j]=min\{f[i$^$k][j]+f[k][j]\}$，其中$i $&$ k = k$。

转移完毕后，跑一个最短路去更新一遍。

那么显然这题的时间复杂度是$O(2^k\times 最短路时间复杂度)$。

但是这题神TM卡SPFA。。。。

我后来改写了$dij$，再加了个避免重复更新的判断，才过了...

 #include<bits/stdc++.h>

 #define M 100005

 #define L long long

 #define INF 1926081719260817LL

 using namespace std;

 struct edge{int u,v,next;}e[M<<]={}; int head[M]={},use=;

 void add(int x,int y,int z){use++;e[use].u=y;e[use].v=z;e[use].next=head[x];head[x]=use;}

 L f[<<][M]={};

 struct node{

     int u; L dis; node(){u=dis=;}

     node(int uu,L diss){u=uu; dis=diss;}

     friend bool operator <(node a,node b){return a.dis>b.dis;}

 }; priority_queue<node> q;

 bool vis[M]={};

 void spfa(L dfn[]){

     memset(vis,,sizeof(vis));

     while(!q.empty()){

         node uu=q.top(); q.pop();

         int u=uu.u;

         if(vis[u]) continue; vis[u]=;

         for(int i=head[u];i;i=e[i].next)

         if(dfn[e[i].u]>dfn[u]+e[i].v){

             dfn[e[i].u]=dfn[u]+e[i].v;

             q.push(node(e[i].u,dfn[e[i].u]));

         }

     }

 }

 int n,m,k,p[]={};

 int main(){

     scanf("%d%d%d",&n,&k,&m);

     for(int i=;i<(<<k);i++)

     for(int j=;j<=n;j++) f[i][j]=INF;

     for(int i=;i<k;i++){

         scanf("%d",p+i);

         f[<<i][p[i]]=;

     }

     for(int i=;i<=m;i++){

         int x,y,z; scanf("%d%d%d",&x,&y,&z);

         add(x,y,z); add(y,x,z);

     }

     for(int i=;i<(<<k);i++){

         for(int j=i;j;j=i&(j-)){

             for(int k=;k<=n;k++)

             f[i][k]=min(f[i][k],f[j][k]+f[i^j][k]);

         }

         for(int k=;k<=n;k++)

         if(f[i][k]!=INF) q.push(node(k,f[i][k]));

         spfa(f[i]);

     }

     L minn=INF;

     for(int i=;i<=n;i++)

     minn=min(minn,f[(<<k)-][i]);

     cout<<minn<<endl;

 }

巴特西

【bzoj5180】[Baltic2016]Cities 斯坦纳树

最新文章

热门文章