代码

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define F(i, l, r) for(int i = (l), _end_ = (int)(r); i <= _end_; ++i)
#define f(i, r, l) for(int i = (r), _end_ = (int)(l); i >= _end_; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define file(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}
inline int read() {
 int x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
    return x * fh;
}
using namespace std;
const int MAX_N = 220000;
int he[200005],to[800005],ne[800005],cost[800005],e;
struct node{
  int u,v,hei,len;
}p[400005];
int fa[200005];
int ls[200005*60],rs[200005*60],mindep[200005*60],dep[200005],lst[200005*60];
int n,m,cnt,root[200005*60];
int len[200005];
void add(int x,int y,int z){
     to[++e]=y;
     ne[e]=he[x];
     he[x]=e;
     cost[e]=z;
}
long long dis[200005];
int h[400005];
#define PII pair<long long,int>
priority_queue<PII,vector<PII> ,greater<PII> >Q;
void spfa(){
    F(i,1,n)dis[i]=1e15;
   dis[1]=0;
   Q.push(make_pair(dis[1],1));
   while(!Q.empty()){
    PII now=Q.top();
    Q.pop();
    for(int i=he[now.second];i;i=ne[i]){
         int v=to[i];
        if(dis[now.second]+cost[i]<dis[v]){
            dis[v]=dis[now.second]+cost[i];
              Q.push(make_pair(dis[v],v));
        }
    }
   }
}
bool cmp(node x,node y){
  return x.hei>y.hei;
}
#define mid ((l+r)>>1)
void built(int &rt,int l,int r){
      rt=++cnt;
      if(l==r){
          lst[rt]=l;
          mindep[rt]=dis[l];
          return ;
      }
     built(ls[rt],l,mid);
     built(rs[rt],mid+1,r);
}
void update(int &rt,int pre,int l,int r,int x,int val){
    rt=++cnt;
    ls[rt]=ls[pre];
    rs[rt]=rs[pre];
    if(l==r){
       mindep[rt]=val;
       lst[rt]=lst[pre];
       return ;
    }
    if(x<=mid)update(ls[rt],ls[pre],l,mid,x,val);
    else update(rs[rt],rs[pre],mid+1,r,x,val);
}
void modify(int &rt,int pre,int l,int r,int x,int val){
   rt=++cnt;
   ls[rt]=ls[pre];
   rs[rt]=rs[pre];
   if(l==r){
       lst[rt]=val;
       mindep[rt]=mindep[pre];
       return ;
   }
   if(x<=mid)modify(ls[rt],ls[pre],l,mid,x,val);
   else modify(rs[rt],rs[pre],mid+1,r,x,val);
}
int querymin(int rt,int l,int r,int x){
       if(l==r)return mindep[rt];
       if(x<=mid)return querymin(ls[rt],l,mid,x);
       else  return querymin(rs[rt],mid+1,r,x);
}
int querypre(int rt,int l,int r,int x){
   if(l==r)return lst[rt];
   if(x<=mid)return querypre(ls[rt],l,mid,x);
   else return querypre(rs[rt],mid+1,r,x);
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y,int id){
    int xx,yy;
    xx=find(x),yy=find(y);
    if(dep[xx]<dep[yy])swap(xx,yy);
    fa[yy]=xx;
    if(dep[yy]==dep[xx])dep[xx]++;
    modify(root[id],root[id-1],1,n,yy,xx);
    if(chkmin(len[xx],len[yy]))update(root[id],root[id],1,n,xx,len[xx]);
}
int main(){
    int t=read();
    while(t--){
    Set(he,0);
    e=0;
    Set(ls,0);
    Set(rs,0);
    Set(root,0);
    cnt=0;
    n=read();
    m=read();
    F(i,1,m){
      p[i].u=read();
      p[i].v=read();
      p[i].len=read();
      p[i].hei=read();
      add(p[i].u,p[i].v,p[i].len);
      add(p[i].v,p[i].u,p[i].len);
    }
    spfa();
    F(i,1,n)fa[i]=i,len[i]=dis[i],dep[i]=1;
    built(root[0],1,n);
    sort(p+1,p+m+1,cmp);
    F(i,1,m){
            int a=p[i].u,b=p[i].v;
            merge(a,b,i);
            h[i]=p[i].hei;
    }
    int q=read(),k=read(),s=read();
    long long lstans=0;
    while(q--){
       int v=read(),p=read();
         v=(v+k*lstans-1)%n+1;
         p=(p+k*lstans)%(s+1);
         int ll=1,rr=m,ret=0;
         while(ll<=rr){
            int Mid=(ll+rr)>>1;
            if(h[Mid]>p){
                ll=Mid+1;
                ret=Mid;
            }
            else rr=Mid-1;
         }
         int Pre;
          while(1){
            Pre=querypre(root[ret],1,n,v);
            if(v==Pre)break;
            v=Pre;
        }
        lstans=querymin(root[ret],1,n,v);
            printf("%lld\n",lstans);
    }
    }
    return 0;
}

评测结果