代码

#pragma GCC optimize(2)
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 400100
#define ll long long
#define fo(i,a,b) for(int i=a,E=b;i<=E;i++)
#define M 20000010

using namespace std;

int l[N+N],v[N+N],nex[N+N],hd[N],top,heap[N],pos[N],d[N],K,n,m,q,a[N],t,S,lg[N];
int fa[N],to[N+N],nxt[N+N],fir[N],tot,cnt,son[M][2],left[M],right[M],opu,opv,opl,opr,rt[N];
int dfl[N],dfr[N],Top,sta[N],que[N],head,tail,siz[N];
ll f[N],mn[20][N];
bool vis[N];
struct road{int u,v,l,a;}r[N];
bool cmp(road a,road b){return a.a>b.a;}

void link(int x,int y,int val){
	l[++top]=val;v[top]=y;nex[top]=hd[x];hd[x]=top;
}

void down(int x){
	for(int y=x+x,z=y+1;y<=top;swap(heap[x],heap[y]),pos[heap[x]]=x,pos[heap[y]]=y,x=y,y=x+x,z=y+1){
		if(f[heap[y]]>f[heap[z]])y=z;
		if(f[heap[x]]<=f[heap[y]])break;
	}
}
void up(int x){
	for(int y=x>>1;y;swap(heap[x],heap[y]),pos[heap[x]]=x,pos[heap[y]]=y,x=y,y=x>>1)
		if(f[heap[x]]>=f[heap[y]])break;
}
int get(){
	int r=heap[1];pos[heap[top]]=1;heap[1]=heap[top--];down(1);return r;
}
void put(int x){
	heap[++top]=x;pos[x]=top;up(top);
}

void dijk(){
	fo(i,1,n)f[i]=1e18,d[i]=i,vis[i]=0;
	f[1]=0;top=0;
	fo(i,1,n)put(i);
	fo(i,1,n){
		int x=get();vis[x]=1;
		for(int o=hd[x];o;o=nex[o])if(!vis[v[o]])
			if(f[v[o]]>f[x]+l[o]){
				f[v[o]]=f[x]+l[o];up(pos[v[o]]);
			}
	}
}

int find(int *a,int v,int l){
	int h=1,t=l,m,r=l;
	while(h<=t)if(a[m=h+t>>1]<=v)t=m-1,r=m;else h=m+1;
	return r;
}

ll getmn(int h,int t){
	int l=lg[t-h+1];
	return min(mn[l][h],mn[l][t-(1<<l)+1]);
}

int get(int x){
	for(;(x=fa[x])!=fa[x];)sta[++Top]=x;
	while(Top)fa[sta[Top--]]=x;return x;
}

void con(int x,int y){
	to[++top]=y;nxt[top]=fir[x];fir[x]=top;
}
void dfs(int x){
	for(head=0,que[tail=1]=x;tail^head;)
		for(int x=que[++head],i=fir[x];i;i=nxt[i])que[++tail]=to[i];
	for(;head;head--){
		int x=que[head];siz[x]=1;
		for(int i=fir[x];i;i=nxt[i])siz[x]+=siz[to[i]];
	}
	dfl[x]=1;
	for(;head<=tail;head++){
		int x=que[head],sum=dfl[x];
		dfr[x]=dfl[x]+siz[x]-1;
		for(int i=fir[x];i;i=nxt[i])dfl[to[i]]=sum+1,sum+=siz[to[i]];
	}
}
void build(int &w,int h,int t){
	w=++cnt;
	if(h==t){
		left[w]=h;right[w]=t;return;
	}left[w]=right[w]=-1;
	int m=h+t>>1;
	build(son[w][0],h,m);build(son[w][1],m+1,t);
}
void cover(int &u,int v,int h,int t){
	u=++cnt;
	if(opl<=h && opr>=t){
		left[u]=opl;right[u]=opr;return;
	}son[u][0]=son[v][0];son[u][1]=son[v][1];
	left[u]=right[u]=-1;
	int m=h+t>>1;
	if(opl<=m)cover(son[u][0],son[v][0],h,m);
	if(opr>m)cover(son[u][1],son[v][1],m+1,t);
}
void query(int w,int h,int t){
	if(left[w]!=-1){
		opu=left[w];opv=right[w];return;
	}int m=h+t>>1;
	if(opl<=m)query(son[w][0],h,m);else query(son[w][1],m+1,t);
}

int main(){
	int T;scanf("%d",&T);
	lg[1]=0;
	fo(i,2,N-1)lg[i]=lg[i>>1]+1;
	while(T--){
		scanf("%d %d",&n,&m);
		top=0;
		memset(hd,0,sizeof hd);
		fo(i,1,m){
			int fr,to,len,lev;scanf("%d %d %d %d",&fr,&to,&len,&lev);
			a[i]=lev;r[i]=(road){fr,to,len,lev};link(fr,to,len);link(to,fr,len);
		}
		sort(r+1,r+m+1,cmp);sort(a+1,a+m+1);fo(i,1,m/2)swap(a[i],a[m+1-i]);
		fo(i,1,m)if(i==1)t=1;else if(a[i]^a[i-1])a[++t]=a[i];
		a[++t]=0;
		dijk();
		top=cnt=0;tot=n;
		fo(i,1,n+n)fa[i]=i;
		memset(fir,0,sizeof fir);
		fo(i,1,m){
			int u=r[i].u,v=r[i].v,A=get(u),B=get(v);
			if(A==B)continue;f[++tot]=1e18;fa[A]=tot;fa[B]=tot;con(tot,A);con(tot,B);
		}top=0;dfs(tot);
		fo(i,1,tot)mn[0][dfl[i]]=f[i];
		fo(j,1,19)fo(i,1,tot)if(tot-i+1>=(1<<j))mn[j][i]=min(mn[j-1][i],mn[j-1][i+(1<<j-1)]);
		fo(i,1,n+n)fa[i]=i;
		build(rt[1],1,tot);
		int las=rt[1],tmp=n,w=1;
		fo(i,1,t){
			if(i>1)rt[i]=rt[i-1];
			while(w<=m && r[w].a>a[i]){
				int u=r[w].u,v=r[w].v,A=get(u),B=get(v);w++;
				if(A==B)continue;++tmp;fa[A]=tmp;fa[B]=tmp;
				opl=opu=dfl[tmp];opr=opv=dfr[tmp];
				cover(rt[i],las,1,tot);las=rt[i];
			}
		}
		scanf("%d %d %d",&q,&K,&S);
		ll lasans=0;
		fo(i,1,q){
			ll u,lev;scanf("%lld %lld",&u,&lev);
			u=(u+K*lasans-1)%n+1;lev=(lev+K*lasans)%(S+1);
			opl=dfl[u];query(rt[find(a,(int)lev,t)],1,tot);
			printf("%lld\n",lasans=getmn(opu,opv));
		}
	}
	return 0;
}

评测结果