代码

#include<bits/stdc++.h>
#include<assert.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define eF(i,u) for(int i=h[u];i;i=nxt[i])
#define ll long long
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;

int n,m,q;
int S[1000001],T[1000001],L[1000001],A[1000001],P[1000001],D[1000005];
inline bool cmp(int i,int j){return A[i]>A[j];}

int h[1000001],nxt[1000001],to[1000001],w[1000001],g[1000001],tot;
inline void ins(int x,int y,int z,int v){nxt[++tot]=h[x];to[tot]=y;w[tot]=z;g[tot]=v;h[x]=tot;}

int dis[1000001],sho[1000001];
priority_queue<pii,vector<pii>,greater<pii> > pq;
void dij(){
	memset(dis,0x3f,sizeof dis);
	memset(sho,0,sizeof sho);
	dis[1]=0;
	pq.push(pii(0,1));
	while(!pq.empty()){
		pii P=pq.top(); pq.pop();
		if(sho[P.second]) continue;
		int u=P.second, d=P.first;
		sho[u]=1;
		eF(i,u) if(dis[to[i]]>d+w[i]){
			dis[to[i]]=d+w[i];
			pq.push(pii(dis[to[i]],to[i]));
		}
	}
}

int rt[1000005],rts=0,RT[1000005];
int Faz[20000005],Siz[20000005],Dis[20000005],ls[20000005],rs[20000005],cnt;
void build(int&i,int l,int r){
	if(!i) i=++cnt;
	if(l==r) {Siz[i]=1; Dis[i]=dis[l]; return;}
	build(ls[i],l,l+r>>1);
	build(rs[i],(l+r>>1)+1,r);
}

void Mdf(int&i,int l,int r,int p,int x,int y,int z){
	ls[++cnt]=ls[i],rs[cnt]=rs[i],i=cnt;
	if(l==r) {Faz[i]=x; Siz[i]=y; Dis[i]=z; return;}
	if(p<=(l+r>>1)) Mdf(ls[i],l,l+r>>1,p,x,y,z);
	else Mdf(rs[i],(l+r>>1)+1,r,p,x,y,z);
}

int Fa(int i,int l,int r,int p){
	if(l==r) return Faz[i];
	if(p<=(l+r>>1)) return Fa(ls[i],l,l+r>>1,p);
	else return Fa(rs[i],(l+r>>1)+1,r,p);
}
pii SD(int i,int l,int r,int p){
	if(l==r) return pii(Siz[i],Dis[i]);
	if(p<=(l+r>>1)) return SD(ls[i],l,l+r>>1,p);
	else return SD(rs[i],(l+r>>1)+1,r,p);
}
int Di(int i,int l,int r,int p){
	if(l==r) return Dis[i];
	if(p<=(l+r>>1)) return Di(ls[i],l,l+r>>1,p);
	else return Di(rs[i],(l+r>>1)+1,r,p);
}
int ff(int rt,int x){
	int d;
	return (d=Fa(rt,1,n,x))?ff(rt,d):x;
}

int main(){
	int Tests;
	scanf("%d",&Tests);
	while(Tests--){
		memset(rt,0,sizeof rt); rts=0;
		memset(RT,0,sizeof RT); cnt=0;
		memset(ls,0,sizeof ls);
		memset(rs,0,sizeof rs);
		int x,y,z,w;
		scanf("%d%d",&n,&m);
		memset(h,0,sizeof h); tot=0;
		F(i,1,m)
			scanf("%d%d%d%d",S+i,T+i,L+i,A+i),
			ins(S[i],T[i],L[i],A[i]),
			ins(T[i],S[i],L[i],A[i]),
			P[i]=i, D[i]=A[i];
		dij();
		sort(P+1,P+m+1,cmp);
		sort(D+1,D+m+1); D[m+1]=0x7fffffff;
		build(rt[0],1,n);
		RT[0]=rt[0];
		F(I,1,m){
			int i=P[I];
			int u=S[i], v=T[i];
			u=ff(rt[rts],u);
			v=ff(rt[rts],v);
			if(u==v) {RT[I]=rt[rts]; continue;}
			pii Pu=SD(rt[rts],1,n,u);
			pii Pv=SD(rt[rts],1,n,v);
			if(Pu.first>Pv.first) swap(Pu,Pv), swap(u,v);
			++rts;
			Mdf(rt[rts]=rt[rts-1],1,n,u,v,Pu.first,Pu.second);
			++rts;
			Mdf(rt[rts]=rt[rts-1],1,n,v,0,Pu.first+Pv.first,min(Pu.second,Pv.second));
			RT[I]=rt[rts];
		}
		int k,S,lstans=0;
		scanf("%d%d%d",&q,&k,&S); ++S;
		F(i,1,q){
			int v,p;
			scanf("%d%d",&v,&p);
			v=(v+k*lstans-1)%n+1;
			p=(p+(ll)k*lstans)%S;
			int y=upper_bound(D+1,D+m+2,p)-D;
			y=m-y+1;
			int d=ff(RT[y],v);
			pii PP=SD(RT[y],1,n,v);
			printf("%d\n",lstans=Di(RT[y],1,n,d));
		}
	}
	return 0;
}

评测结果