代码

#pragma GCC optimize ("O2")
#include <bits/stdc++.h>
#define inline inline __attribute__((always_inline))
using namespace std;

const int N=2e5+5,M=N<<2;
int To[M],Ne[M],St[N],Wg[M],en,n,dis[N],m;
inline void addedge(int u,int v,int w) {
	To[++en]=v,Ne[en]=St[u],St[u]=en;Wg[en]=w;
	To[++en]=u,Ne[en]=St[v],St[v]=en;Wg[en]=w;
}

struct et {
	int u,v,a;
	inline et(int u=0,int v=0,int a=0):u(u),v(v),a(a) {}
}e[M];

namespace persufs {
	struct tn {
		int ls,rs,fa,rk,dis,pos,ver;
		inline void clr() {ls=rs=fa=rk=dis=pos=ver=0;}
	}t[N<<6];
	int rt[N],nn;
	#define lson t[Node].ls
	#define rson t[Node].rs
	void Build(int& Node,int l,int r) {
		if(Node==0) Node=++nn;
		t[Node].ver=0;
		if(l==r) {
			t[Node].fa=t[Node].rk=0,t[Node].pos=l;
			t[Node].dis=dis[l];
			return;
		}
		int mid=(l+r)>>1;
		lson=rson=0;
		Build(lson,l,mid);
		Build(rson,mid+1,r);
	}
	inline void clear() {memset(rt,0,sizeof(rt)); nn=0; Build(rt[0],1,n);}
	
	int fa_=-1,rk_=-1,dis_=-1,ver_=0;
	void auxModify(int pNode,int& Node,int l,int r,int pos) {
		if(Node==0) {
			Node=++nn;
			t[Node].clr();
		}
		t[Node].ver=ver_;
		if(l==r) {
			t[Node]=t[pNode]; t[Node].ver=ver_;
			if(fa_!=-1) t[Node].fa=fa_; if(rk_!=-1) t[Node].rk=rk_; if(dis_!=-1) t[Node].dis=dis_;
			return;
		}
		int mid=(l+r)>>1;
		if(pos<=mid) {
			if(t[lson].ver!=ver_) lson=0;
			if(t[rson].ver!=ver_) rson=t[pNode].rs;
			auxModify(t[pNode].ls,lson,l,mid,pos);
		}
		else {
			if(t[lson].ver!=ver_) lson=t[pNode].ls;
			if(t[rson].ver!=ver_) rson=0;
			auxModify(t[pNode].rs,rson,mid+1,r,pos);
		}
	}
	inline void Modify(int ver,int loc,int fa,int rk,int dis) {
		fa_=fa,rk_=rk,dis_=dis,ver_=ver;
		auxModify(rt[ver-1],rt[ver],1,n,loc);
	}
	tn auxQuery(int Node,int l,int r,int pos) {
		if(l==r) return t[Node];
		int mid=(l+r)>>1;
		if(pos<=mid) return auxQuery(lson,l,mid,pos);
		else return auxQuery(rson,mid+1,r,pos);
	}
	inline tn getfa(int ver,int pos) {
		tn tmp=auxQuery(rt[ver],1,n,pos);
		while(tmp.fa!=0) tmp=auxQuery(rt[ver],1,n,tmp.fa);
		return tmp;
	}
	inline void Union(int cver,int p1,int p2) {
		tn f1=getfa(cver,p1),f2=getfa(cver,p2);
		if(f1.pos==f2.pos) {
			rt[cver+1]=rt[cver];
			return;
		}
		if(f1.rk<=f2.rk) {
			Modify(cver+1,f1.pos,f2.pos,-1,-1);
			Modify(cver+1,f2.pos,-1,(f1.rk==f2.rk ? f2.rk+1 : -1),min(f2.dis,f1.dis));
		}
		else {
			Modify(cver+1,f2.pos,f1.pos,-1,-1);
			Modify(cver+1,f1.pos,-1,-1,min(f1.dis,f2.dis));
		}
	}
}

inline char nc() {
	static char buf[1001001], *p1 = buf, *p2 = buf;
	return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, 1 << 12, stdin), p1 == p2) ? EOF : *p1++;
}

inline int read() {
	static char c;
	c=nc();
	while(!('0'<=c&&c<='9')) c=nc();
	int x=0;
	for(;'0'<=c&&c<='9';c=nc()) x=x*10+c-48;
	return x;
}

inline void write(int k) {
	static char buf[2333];
	if(k==0) return (void)putchar(48);
	int tp=0;
	while(k) buf[tp++]=k%10+48,k/=10;
	while(--tp>=0) putchar(buf[tp]);
}

inline bool compe(const et& lhs,const et& rhs) {return lhs.a>rhs.a;}

struct het {
	int dis,v;
	inline het(int dis=0,int v=0):dis(dis),v(v) {}
};
inline bool operator<(const het& lhs,const het& rhs) {return lhs.dis<rhs.dis;}
inline bool operator>=(const het& lhs,const het& rhs) {return !(lhs<rhs);}
namespace heap {
	het h[N<<1];
	int sz;
	inline void clear() {memset(h,0,sizeof(h)); sz=0;}
	inline void push(het k) {
		int i=(++sz);
		for(int f=i>>1;f&&k<h[f];i=f,f>>=1) h[i]=h[f];
		h[i]=k;
	}
	inline het poptop() {
		int i=1;
		het ret=h[1],k=h[sz--];
		for(int s=2;s<=sz;i=s,s=i<<1) {
			if((s|1)<=sz&&h[s|1]<h[s]) s|=1;
			if(h[s]>=k) break;
			h[i]=h[s];
		}
		h[i]=k;
		return ret;
	}
}

bool vi[N];
inline void dijkstra() {
	memset(dis,127,sizeof(dis)); dis[1]=0;
	memset(vi,0,sizeof(vi));
	heap::push(het(0,1));
	while(heap::sz!=0) {
		het tmp=heap::poptop();
		int u=tmp.v;
		if(vi[u]) continue;
		dis[u]=tmp.dis;
		vi[u]=1;
		for(int i=St[u];i;i=Ne[i]) {
			if(dis[To[i]]>dis[u]+Wg[i]) {
				dis[To[i]]=dis[u]+Wg[i];
				heap::push(het(dis[To[i]],To[i]));
			}
		}
	}
}

inline int findedge(int p) {
	int l=1,r=m,mid;
	while(l<=r) {
		mid=(l+r)>>1;
		if(e[mid].a>p) l=mid+1; else r=mid-1;
	}
	return (e[r].a<=p ? r : l);
}

int main() {
	//freopen("return.in","r",stdin);
	//freopen("return.out","w",stdout);
	
	int T=read();
	while(T--) {
		n=read(),m=read();
		
		en=0; memset(St,0,sizeof(St));
		for(int i=1,u,v,l,a;i<=m;++i) {
			u=read(),v=read(),l=read(),a=read();
			addedge(u,v,l);
			e[i]=et(u,v,a);
		}
		dijkstra();
		//for(int i=1;i<=n;++i) printf("%d ",dis[i]);
		persufs::clear();
		e[0].a=e[m+1].a=2139062143;
		sort(e+1,e+m+1,compe);
		for(int i=1;i<=m;++i) {
			//printf("%d %d %d\n",e[i].u,e[i].v,e[i].a);
			persufs::Union(i-1,e[i].u,e[i].v);
		}
		//puts("");
		int Q=read(),K=read(),S=read(),lans=0;
		while(Q--) {
			int u=read(),p=read();
			u=(u+1ll*K*lans-1)%n+1;
			p=(p+1ll*K*lans)%(S+1);
			persufs::tn tmp=persufs::getfa(findedge(p)-1,u);
			lans=tmp.dis;
			//printf("%d %d\n",findedge(p)-1,tmp.pos);
			write(lans); putchar('\n');
		}
	}
	
	return 0;
}

评测结果