代码

#include<bits/stdc++.h>
#define ll long long
#define INF 1e10
using namespace std;
struct Info{int nu,ne,qu;}a[800010];
struct Onfo{int x,y,p;}e[400010];
struct seg{int ls,l,r;ll rs;}t[10000010];
struct pp{int nu,we;}f[400010];
int b[200010],m,n,opt,num,x,y,z,p,ro[400010],nf,si[400010],q,k,ss,v,vi[200010],s[200010],ns;
ll di[200010],lan;
void jb(int x,int y,int z){a[++num].nu=y;a[num].ne=b[x];b[x]=num;a[num].qu=z;}
priority_queue<pair<ll,int> > Q;
bool comp(const Onfo &a,const Onfo &b){return a.p>b.p;}
int build(int l,int r){
	num++;t[num].l=l;t[num].r=r;
	if (l==r){t[num].ls=l,t[num].rs=di[l];return num;}
	else{
		int pp=num;
		t[pp].ls=build(l,(l+r)/2);
		t[pp].rs=build((l+r)/2+1,r);
		return pp;
	}
}
void dij(){
    for (int i=1;i<=n;i++) {vi[i]=false;di[i]=2147483647;}
 	Q.push(make_pair(0,1));
    di[1]=0;
    while (!Q.empty()){
        int x=Q.top().second;
        Q.pop();
        if (vi[x]) continue;
        vi[x]=true;
        for (int y=b[x];y;y=a[y].ne){
        	if (di[a[y].nu]>di[x]+a[y].qu){
        		di[a[y].nu]=di[x]+a[y].qu;
        		Q.push(make_pair(-di[a[y].nu],a[y].nu));
			}
		}
    }
}
int que(int nu,int we){
	if (t[nu].l==t[nu].r) return t[nu].ls;
	if (we<=(t[nu].l+t[nu].r)/2) return que(t[nu].ls,we);
	else return que(t[nu].rs,we);
}
ll ques(int nu,int we){
	if (t[nu].l==t[nu].r) return t[nu].rs;
	if (we<=(t[nu].l+t[nu].r)/2) return ques(t[nu].ls,we);
	else return ques(t[nu].rs,we);
}
int fa(int x,int ro){
	while (1){
		int y=que(ro,x);
		if (x==y) return x;
		x=y;
	}
}
void build1(int no,int la,ll x,int y,int we){
	t[no]=t[la];
	if (t[no].l==t[no].r){
		t[no].ls=y;t[no].rs=x;
	}else{
		if (we<=(t[no].l+t[no].r)/2){
			t[no].ls=++num;
			build1(num,t[la].ls,x,y,we);
		}else{
			t[no].rs=++num;
			build1(num,t[la].rs,x,y,we);
		}
	}
}
int main(){
	freopen("return.in","r",stdin);
	freopen("return.out","w",stdout);
	scanf("%d",&opt);
	while(opt--){
		memset(b,0,sizeof(b));num=0;
		scanf("%d %d",&n,&m);
		e[0].p=2e9;
		for (int i=1;i<=m;i++){
			scanf("%d %d %d %d",&x,&y,&z,&p);
			jb(x,y,z);jb(y,x,z);
			e[i].x=x;e[i].y=y;e[i].p=p;
		}
		sort(e+1,e+m+1,comp);
		dij();
		num=0;ro[0]=build(1,n);
		for (int i=1;i<=n;i++)si[i]=0;
		for (int i=1;i<=m;i++){
			int x=fa(e[i].x,ro[i-1]),y=fa(e[i].y,ro[i-1]);
			if (x!=y){
				if (si[x]>si[y]){
					z=++num;
					build1(z,ro[i-1],min(ques(ro[i-1],x),ques(ro[i-1],y)),x,x);
					ro[i]=++num;
					build1(ro[i],z,que(ro[i-1],y),x,y);
				}else{
					if (si[x]==si[y])si[y]++;
					z=++num;
					build1(z,ro[i-1],min(ques(ro[i-1],x),ques(ro[i-1],y)),y,y);			
					ro[i]=++num;
					build1(ro[i],z,ques(ro[i-1],x),y,x);					
				}
			}else{
				ro[i]=ro[i-1];
			}
		}
		scanf("%d %d %d",&q,&k,&ss);
		while (q--){
			scanf("%d %d",&v,&p);
			v=((ll)v+k*lan-1+n)%n+1;
			p=(p+k*lan)%(ss+1);
			int l=0,r=m,mid;
			while (l+1<r){
				mid=(l+r)/2;
				if (e[mid].p>p)l=mid;else r=mid;
			}
			if (e[r].p>p) l=r;
			x=fa(v,ro[l]);
			lan=ques(ro[l],x);
			cout<<lan<<endl;
		}
	}
	return 0;
}

评测结果