bzoj 4398 福慧双修 —— 二进制分组+多起点最短路

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

按二进制每一位是 0/1 把 1 号点的儿子分成两组，分别作为起点和终点跑多起点最短路，最优解的起点和终点总有一次会被分到不同组里；

太久没写 dijkstra 竟然WA了4次...别忘了 priority_queue 是大根堆-_-，还要注意循环计数的 i，j 不要重了...

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int const xn=,xm=1e5+,inf=0x3f3f3f3f;

int n,m,hd[xn],ct,nxt[xm<<],to[xm<<],w[xm<<],dis[xn],ans;

bool vis[xn],in[xn],out[xn];

struct N{

  int d,id;

  bool operator < (const N &y) const

  {return d>y.d;}//>

};

priority_queue<N>q;

int rd()

{

  int ret=,f=; char ch=getchar();

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

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

  return f?ret:-ret;

}

void add(int x,int y,int z){to[++ct]=y; nxt[ct]=hd[x]; w[ct]=z; hd[x]=ct;}

void dij()

{

  memset(vis,,sizeof vis);

  while(q.size())

    {

      int x=q.top().id; q.pop();

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

      for(int i=hd[x],u;i;i=nxt[i])

    {

      if(vis[u=to[i]]||(u==&&out[x])||(x==&&in[u]))continue;

      if(dis[u]>dis[x]+w[i])

        dis[u]=dis[x]+w[i],q.push((N){dis[u],u});

    }

    }

  ans=min(ans,dis[]);

}

int main()

{

  n=rd(); m=rd();

  for(int i=,x,y,z,k;i<=m;i++)

    {

      x=rd(); y=rd(); z=rd(); k=rd();

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

    }

  int cnt=,t=n; while(t)cnt++,t/=; ans=inf;

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

    {

      memset(dis,0x3f,sizeof dis); while(q.size())q.pop();

      for(int j=hd[],u;j;j=nxt[j])

    {

      in[u=to[j]]=; out[u]=;

      if(u&(<<i))dis[u]=w[j],out[u]=,q.push((N){w[j],u});

      else in[u]=;

    }

      dij();

      memset(dis,0x3f,sizeof dis); while(q.size())q.pop();

      for(int j=hd[],u;j;j=nxt[j])

    {

      if(in[u=to[j]])in[u]=,out[u]=,dis[u]=w[j],q.push((N){w[j],u});

      else out[u]=,in[u]=;

    }

      dij();

    }

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

  return ;

}