代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

#define Death Komachi 
#define Uni :All right
#define REP(i,a,b) for(int i=(a),i##_end_=(b);i<i##_end_;++i)
#define DREP(i,a,b) for(int i=(a),i##_end_=(b);i>i##_end_;--i)
#define LREP(i,a) for(int i=Head[a];i;i=Next[i])
#define N 200004
#define M 400004
#define LL long long

void Rd(int &x){
	static char c;x=0;
	while((c=getchar())<48);
	do x=(x<<3)+(x<<1)+(c^48);
	while((c=getchar())>47);
}
void Wt(LL x){
	static char stk[24];int l=0;
	do stk[l++]=x%10^48;
	while(x/=10);
	while(l)putchar(stk[--l]);
	puts("");
}
int T,n,m,q,K,S;
int Next[M<<1],V[M<<1],W[M<<1],Head[N],tot;
LL Dis[N];
void Add_Edge(int u,int v,int w){
	Next[++tot]=Head[u],V[Head[u]=tot]=v,W[tot]=w;
}
struct Path{
	int x;LL w;
	bool operator <(const Path &_)const{
		return w>_.w;
	}
};
priority_queue<Path>PQ;
void Dij(){
	memset(Dis,63,sizeof(Dis));
	PQ.push((Path){1,Dis[1]=0ll});
	while(!PQ.empty()){
		int x=PQ.top().x,y;
		LL w=PQ.top().w;PQ.pop();
		if(w!=Dis[x])continue;
		LREP(i,x)if(Dis[y=V[i]]>w+W[i])
			PQ.push((Path){y,Dis[y]=w+W[i]});
	}
}
struct Edge{
	int u,v,a;
	bool operator <(const Edge &_)const{
		return a<_.a;
	}
}E[M];
static const int MX=M*80;
struct Node{int f,h;LL s;}D[MX];
int Rt[M],Lp[MX],Rp[MX],trt;
#define lson l,mid,Lp[p]
#define rson mid+1,r,Rp[p]
void Init(int l,int r,int &p){
	p=++trt;
	if(l==r)D[p]=(Node){l,1,Dis[l]};
	else{
		int mid=l+r>>1;
		Init(lson);
		Init(rson);
	}
}
void Updata(int l,int r,int &p,int old,int a,Node &d){
	p=++trt;
	if(l==r)D[p]=d;
	else{
		int mid=l+r>>1;
		if(a<=mid)Rp[p]=Rp[old],Updata(lson,Lp[old],a,d);
		else Lp[p]=Lp[old],Updata(rson,Rp[old],a,d);
	}
}
Node Query(int l,int r,int p,int a){
	if(l==r)return D[p];
	else{
		int mid=l+r>>1;
		return a<=mid?Query(lson,a):Query(rson,a);
	}
}
Node From(int f,int x){
	while(1){
		Node Tmp=Query(1,n,Rt[f],x);
		if(Tmp.f==x)return Tmp;
		x=Tmp.f;
	}
}
int Fa[M];
int From(int x){return x==Fa[x]?x:Fa[x]=From(Fa[x]);}
void Union(int f,int t,int x,int y){
	int ta=From(x),tb=From(y);
	if(ta==tb)return;
	Node a=Query(1,n,Rt[f],ta),b=Query(1,n,Rt[f],tb);
	if(a.h<b.h)swap(a,b),swap(x,y),swap(ta,tb);
	Node Tmpa=a,Tmpb=b;
	Tmpb.f=a.f,Tmpa.h+=a.h==b.h,Tmpa.s=min(a.s,b.s);
	
	Fa[tb]=ta;
	Updata(1,n,Rt[t],Rt[t],ta,Tmpa);
	Updata(1,n,Rt[t],Rt[t],tb,Tmpb);
}

int main(){
//	freopen("return.in","r",stdin);
//	freopen("return.out","w",stdout);
	
	Rd(T);
	while(T--){
		Rd(n),Rd(m);
		memset(Head,tot=0,sizeof(Head));
		REP(i,0,m){
			int u,v,l,a;
			Rd(u),Rd(v),Rd(l),Rd(a);
			Add_Edge(u,v,l);
			Add_Edge(v,u,l);
			E[i]=(Edge){u,v,a};
		}
		Dij();
//		REP(i,1,n+1)cerr<<Dis[i]<<' ';cerr<<endl;

		sort(E,E+m);
		Rt[m]=trt=0;
		Init(1,n,Rt[m]);
		REP(i,1,n+1)Fa[i]=i;
		DREP(i,m-1,-1)Rt[i]=Rt[i+1],Union(i+1,i,E[i].u,E[i].v);
		
		Rd(q),Rd(K),Rd(S),S++;
		LL Ans=0;
		while(q--){
			int v,a;
			Rd(v),Rd(a);
			v=(v+K*Ans-1)%n+1;
			a=(a+K*Ans)%S;
			
			int p=upper_bound(E,E+m,(Edge){0,0,a})-E;
			Node t=From(p,v);
			Wt(Ans=t.s);
		}
	}
	return 0;
}

评测结果