代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200100,M=800100;
int w[M],ne[M],la[N],len[M],at[M];
int fa[N],pr[N],md[N],vis[N],size[N];
int s[N],d[N*100],n,m,T,t,Q,K,S;
int sl[N],sr[N],lg[N];
struct sns{int fr,pr,to,md;}c[M];
bool comp2(sns a,sns b){
	if (a.to==b.to)return a.pr>b.pr;
	return a.to<b.to;
}
struct edge{int x,y,l,a;}b[M];
void link(int x,int y,int l,int a){
	w[++t]=y;
	ne[t]=la[x];
	la[x]=t;
	len[t]=l;
	at[t]=a;
}
bool comp(edge a,edge b){return a.a>b.a;}
int gf(int x){return fa[x]==x?x:gf(fa[x]);}
void merge(int x,int y,int at){
	if (x==y)return;
	if (size[x]<size[y])swap(x,y);
	fa[y]=x;
	size[x]=max(size[x],size[y]+1);
	pr[y]=at;
	md[x]=min(md[x],md[y]);
}
int read(){
	char e=getchar();
	while (!('0'<=e&&e<='9'))e=getchar();
	int w=0;
	for (;'0'<=e&&e<='9';e=getchar())w=w*10+e-'0';
	return w;
}
int main(){
for (T=read();T--;){
	memset(la,0,sizeof la);
	n=read();m=read();
	for (int i=2;i<=2*n;i++)lg[i]=lg[i>>1]+1;
	for (int i=1;i<=n;i++)fa[i]=i,pr[i]=1<<30,size[i]=1;
	t=0;
	for (int i=1;i<=m;i++){
		int x=read(),y=read(),l=read(),a=read();
//		scanf("%d%d%d%d",&x,&y,&l,&a);
		b[i]=(edge){x,y,l,a};
		link(x,y,l,a);
		link(y,x,l,a);
	}
	memset(s,127,sizeof s);
	int l=0,r=1;d[1]=1;s[1]=0;vis[1]=1;
	while (l<r){
		int x=d[++l];
		for (int y=la[x];y;y=ne[y]){
			int z=w[y];
			if (s[z]>s[x]+len[y]){
				s[z]=s[x]+len[y];
				if (!vis[z]){
					vis[z]=1;
					d[++r]=z;
					if (s[z]<s[d[l+1]])
					swap(d[r],d[l+1]);
				}
			}
		}
		vis[x]=0;
	}
	for (int i=1;i<=n;i++)md[i]=s[i];
	sort(b+1,b+m+1,comp);
	for (int i=1;i<=m;i++)merge(gf(b[i].x),gf(b[i].y),b[i].a);
	t=0;
	for (int i=1;i<=n;i++){
		if (fa[i]!=i)c[++t]=(sns){i,pr[i],fa[i],md[i]};
		c[++t]=(sns){i,1<<30,i,s[i]};
	}
	sort(c+1,c+t+1,comp2);
	for (int i=2;i<=t+1;i++){
		if (c[i].to==c[i-1].to)c[i].md=min(c[i].md,c[i-1].md);
		else sl[c[i].to]=i;
	}
	sl[n+1]=t+1;
	int lasans=0;
	for (Q=read(),K=read(),S=read();Q--;){
		int v=read(),p=read(),can=0;
//		scanf("%d%d",&v,&p);
		v=(v+K*lasans-1)%n+1;
		p=(p+K*lasans)%(S+1);
		while (fa[v]!=v&&pr[v]>p)v=fa[v],can=1;
		int k=sl[v];
		for (int i=1<<lg[sl[v+1]-sl[v]];i;i>>=1)
			if (c[k+i].to==v&&c[k+i].pr>p)k+=i;
		printf("%d\n",lasans=min(c[k].md,s[v]));
		
	}
}} 

评测结果