代码

#include<cstring>
#include<cstdio>
#include<algorithm>
#define fo(i,a,b)for(int i=a;i<=b;i++)
#define fd(i,a,b)for(int i=b;i>=a;i--)
#define link(x,y,l)(ne[++js]=la[x],la[x]=js,to[js]=y,le[js]=l)
#define ff(i,x)for(int i=la[x];i;i=ne[i])
#define link2(x,y)(ne2[++js]=la2[x],la2[x]=js,to2[js]=y)
#define ff2(i,x)for(int i=la2[x];i;i=ne2[i])
#define ll long long
#define pu(x) putchar(x)
#define min(a,b)(a<b?a:b)
#define nw(v)(tr[++ts]=tr[v],v=ts)
using namespace std;
const int N=2e5+5,inf=2e9;
int t,n,m,x,y,l,a,la[N],ne[N*4],to[N*4],le[N*4],f[N],js;
int d[N],dy[N],nu,fa[N],rk[N],st[N],en[N],df[N],ds,mf[N];
int la2[N],ne2[N*2],to2[N*2];
int rt[N*2],ts;
int q,k,s,v,p,las;
int pl,pr;
struct no{
	int x,y,a,fx,fy;
	no(int _x,int _y,int _a){x=_x;y=_y;a=_a;}
	no(){}
}b[N*2];
struct tree{int v,l,r;}tr[N*50];
void R(int &n){
	char c;for(n=0;(c=getchar())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=getchar())n=n*10+c-48;
}
void P(int n){
	if(!n){pu('0');pu('\n');return;}
	char c[20];int j=0;
	for(;n;n/=10)c[++j]=n%10+48;
	while(j)pu(c[j--]);pu('\n');
}
void up(int x){
	for(int y;y=x>>1,f[d[y]]>f[d[x]];dy[d[x]]=x,x=y)swap(d[x],d[y]);
	dy[d[x]]=x;
}
void dw(int x){
	for(int y;y=x<<1,y<=nu&&f[d[y]]<f[d[x]]||y<nu&&f[d[y|1]]<f[d[x]];swap(d[x],d[y]),dy[d[x]]=x,x=y)
		if(y<nu&&f[d[y|1]]<f[d[y]])y++;
	dy[d[x]]=x;
}
void dij(){
	fo(i,1,n)f[i]=inf,d[i]=dy[i]=i;
	nu=n;f[1]=0;
	for(;nu;){
		x=d[1];d[1]=d[nu--];dw(1);
		ff(i,x)if(f[x]+le[i]<f[to[i]])
			f[to[i]]=f[x]+le[i],up(dy[to[i]]);
	}
}
bool cmp(no x,no y){return x.a>y.a;}
int get_f(int x){
	while(fa[x]!=x)x=fa[x];
	return x;
}
void find(int x){
	st[x]=++ds;df[ds]=x;
	ff2(i,x)find(to2[i]);
	en[x]=ds;
}
void build(int &v,int l,int r){
	v=++ts;
	if(l==r){
		tr[v].v=f[df[l]];
		return;
	}
	int m=l+r>>1;
	build(tr[v].l,l,m);build(tr[v].r,m+1,r);
	tr[v].v=-1;
}
void down(int v){
	tr[tr[v].r].v=tr[tr[v].l].v=tr[v].v;tr[v].v=-1;
}
void ch(int &v,int l,int r,int fl){
	nw(v);
	if(pl<=l&&r<=pr){
		tr[v].v=fl;
		return;
	}
	if(tr[v].v>=0)nw(tr[v].l),nw(tr[v].r),down(v);
	int m=l+r>>1;
	if(pl<=m)ch(tr[v].l,l,m,fl);
	if(m<pr)ch(tr[v].r,m+1,r,fl);
}
void deal_egde(){
	sort(b+1,b+m+1,cmp);
	fo(i,1,n)fa[i]=i,rk[i]=1;
	js=0;
	int fx,fy;
	fo(i,1,m){
		x=b[i].x;y=b[i].y;
		fx=get_f(x),fy=get_f(y);
		b[i].fx=fx;b[i].fy=fy;
		if(fx!=fy){
			if(rk[fx]<rk[fy])swap(x,y),swap(fx,fy),swap(b[i].fx,b[i].fy);
			rk[fx]+=rk[fx]==rk[fy];
			fa[fy]=fx;
			link2(fx,fy);
		}
	}
	fo(i,1,n)la[i]=0,mf[i]=f[i];
	fo(i,1,n){
		ds=0;
		ff2(j,i)d[++ds]=to2[j];
		la2[i]=0;
		fo(j,1,ds)link2(i,d[j]);
	}
	ds=js=0;
	find(get_f(1));
	build(rt[0],1,n);
	fo(i,1,m){
		fx=b[i].fx,fy=b[i].fy;
		rt[i]=rt[i-1];
		if(fx!=fy){
			mf[fx]=min(mf[fx],mf[fy]);
			pl=st[fx];pr=en[fy];
			ch(rt[i],1,n,mf[fx]);
		}
	}
}
int main(){
	for(R(t);t--;){
		R(n);R(m);js=ts=0;
		fo(i,1,n)la[i]=la2[i]=0;
		fo(i,1,m)R(x),R(y),R(l),R(a),link(x,y,l),link(y,x,l),b[i]=no(x,y,a);
		dij();
		deal_egde();
		las=0;
		for(R(q),R(k),R(s);q--;){
			R(v);R(p);v=(v+k*las-1)%n+1;p=(p+k*las)%(s+1);
			las=0;
			for(int l=1,r=m,mi;mi=l+r>>1,l<=r;)if(b[mi].a>p)las=mi,l=mi+1;else r=mi-1;
			p=rt[las];
			for(int l=1,r=n,x=st[v],m;m=l+r>>1,tr[p].v<0;)if(x<=m)p=tr[p].l,r=m;else p=tr[p].r,l=m+1;
			las=tr[p].v;
			P(las);
		}
	}
}

评测结果