bzoj 4398 福慧双修——二进制分组

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4398

如果枚举1号点走哪些点出去，就从那些点出发跑多源最短路即可。最短路不会重复经过一条边。

怎样枚举较优？需要枚举到答案的起点在一组、终点在另一组；考虑按点的编号二进制分组，即枚举每一位，为0的在一组，为1的在另一组。

因为两个点编号不同，所以二进制表示至少有1位不同，即任意两个点一定一度被分到过两个组里。

好像还有构造新图的更快的做法。不过也没管。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int N=4e4+,M=1e5+,K=;

int n,m,mx,hd[N],xnt=,to[M<<],nxt[M<<],w[M<<];

int dis[N],sta[N],top,ans=1e9,bin[K];

bool vis[N],use[M];

priority_queue<pair<int,int> >q;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return fx?ret:-ret;

}

void add(int x,int y,int z)

{

  to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z;

}

void init()

{

  int k=n;while(k)k>>=,mx++;mx--;

  bin[]=;for(int i=;i<=mx;i++)bin[i]=bin[i-]<<;

}

void dj()

{

  memset(vis,,sizeof vis);

  while(q.size())

    {

      int k=q.top().second;q.pop();

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

      for(int i=hd[k],v;i;i=nxt[i])

    if(!use[i>>]&&dis[v=to[i]]>dis[k]+w[i])

      {

        dis[v]=dis[k]+w[i];

        q.push(make_pair(-dis[v],v));

      }

    }

  ans=min(ans,dis[]);

}

int main()

{

  n=rdn(); m=rdn(); init();

  for(int i=,u,v,z1,z2;i<=m;i++)

    {

      u=rdn();v=rdn();z1=rdn();z2=rdn();

      add(u,v,z1);add(v,u,z2);

    }

  for(int i=hd[];i;i=nxt[i])sta[++top]=i;

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

    {

      memset(dis,0x3f,sizeof dis);

      for(int j=;j<=top;j++)

    {

      int k=sta[j];

      if(!(to[k]&bin[i]))

        {

          q.push(make_pair(-w[k],to[k]));use[k>>]=;

          dis[to[k]]=w[k];

        }

    }

      dj();

      memset(dis,0x3f,sizeof dis);

      for(int j=;j<=top;j++)

    {

      int k=sta[j];

      if(to[k]&bin[i])

        {

          q.push(make_pair(-w[k],to[k]));use[k>>]=;

          dis[to[k]]=w[k];

        }

      else use[k>>]=;

    }

      dj();

      for(int j=;j<=top;j++)

    if(to[sta[j]]&bin[i])use[sta[j]>>]=;

    }

  printf("%d\n",ans==1e9?-:ans);

  return ;

}