GXOI/GZOI2019 旅行者

题目链接：戳我

这是同学出的题，真心神仙qwq

我们进行二进制分组，因为如果答案是\(k_i\)和\(k_j\)之间的距离的话，他们的编号必定在某一位上不一样。
所以这样子做是对的。跑dij的次数降低到2*log次。

不过最好还是不要像我一样懒，分组之后重新加边，不加O2会慢死的........

#include
#include
#include
#include
#include
#include
#include
#define ss 0
#define tt n+1
#define MAXN 100010
#define MAXM 500010
using namespace std;
int n,m,t,T,k,cnt_a,cnt_b;
int head[MAXN],done[MAXN],kkk[MAXN];
long long ans;
long long dis[MAXN];
vectorG[MAXN];
struct Node
{
    int u;
    long long d;
    friend bool operator < (Node x,Node y)
    {return x.d>y.d;}
};
struct Edge{int nxt,to,dis;}edge[MAXM<<1];
struct Line{int x,y,w;}line[MAXM];
inline void add(int from,int to,int dis)
{
    // printf("[%d %d] %d\n",from,to,dis);
    edge[++t].nxt=head[from],edge[t].to=to,edge[t].dis=dis;
    head[from]=t;
}

inline void dij(int s)
{
    priority_queueq;
    for(int i=0;i<=n+1;i++) dis[i]=0x3f3f3f3f,done[i]=0;
    dis[s]=0;
    q.push((Node){s,0});
    while(!q.empty())
    {
        int u=q.top().u;q.pop();
        if(done[u]) continue;
        done[u]=1;
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].dis)
            {
                dis[v]=dis[u]+edge[i].dis;
                q.push((Node){v,dis[v]});
            }
        }
    }
}
inline void solve_1(int x)
{
    t=0;
    memset(head,0,sizeof(head));
    for(int i=1;i<=k;i++)
    {
        if(kkk[i]&(1<