代码

#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N=3e5+10,M=6e5+10;
struct side{
	int to,w1,nt;
}s[M<<1];
struct note{
	int x,y,w2;
	inline bool operator < (const note lyf) const {return w2>lyf.w2;}
}e[M];
struct dui{
	int d,w;
	inline bool operator < (const dui lyf) const {return w>lyf.w;}
};
struct tree{
	int lt,rt,f,d,w;
}t[20000010];
int ti,n,m,num,x,y,w1,w2,h[N],ww[M],len,now,Q,K,S,dis[N],ans;
int root[M],size;
bool b[N];
priority_queue <dui> que;

inline char nc(void){
	static char ch[100010],*p1=ch,*p2=ch;
	return p1==p2&&(p2=(p1=ch)+fread(ch,1,100010,stdin),p1==p2)?EOF:*p1++;
}

inline void read(int &a){
	char c=nc();int f=1;
	for (;!isdigit(c);c=nc()) if (c=='-') f=-1;
	for (a=0;isdigit(c);a=(a<<3)+(a<<1)+c-'0',c=nc());
	return (void)(a*=f);
}

inline void add(int x,int y,int w1){
	s[++num]=(side){y,w1,h[x]},h[x]=num;
	s[++num]=(side){x,w1,h[y]},h[y]=num;
}

inline void dij(void){
	while (!que.empty()) que.pop();
	memset(dis,0x7f,sizeof dis),memset(b,0,sizeof b);
	dis[1]=0,que.push((dui){1,0});
	while (!que.empty()){
		dui p=que.top();que.pop();
		if (b[p.d]) continue; b[p.d]=1;
		for (int i=h[p.d]; i; i=s[i].nt)
			if (dis[s[i].to]>dis[p.d]+s[i].w1)
				dis[s[i].to]=dis[p.d]+s[i].w1,que.push((dui){s[i].to,dis[s[i].to]});
	}
	return;
}

inline bool cmp(int a,int b){return a>b;}

#define mid (l+r>>1)
inline void build(int &k,int l,int r){
	k=++size;
	if (l==r) return (void)(t[k].f=l,t[k].w=dis[l]);
	build(t[k].lt,l,mid),build(t[k].rt,mid+1,r);
}

inline int query(int k,int l,int r,int wz){
	if (l==r) return k;
	if (wz<=mid) return query(t[k].lt,l,mid,wz);
	return query(t[k].rt,mid+1,r,wz);
}

inline int gf(int rt,int x){
	int fa=query(rt,1,n,x);
	return t[fa].f==x?fa:gf(rt,t[fa].f);
}

inline void change_w(int &k,int pre,int l,int r,int wz,int W){
	t[k=++size]=t[pre];
	if (l==r) return (void)(t[k].w=W);
	if (wz<=mid) change_w(t[k].lt,t[pre].lt,l,mid,wz,W);
	else change_w(t[k].rt,t[pre].rt,mid+1,r,wz,W);
}

inline void updata(int &k,int pre,int l,int r,int wz,int fa){
	t[k=++size]=t[pre];
	if (l==r) return (void)(t[k].f=fa);
	if (wz<=mid) updata(t[k].lt,t[pre].lt,l,mid,wz,fa);
	else updata(t[k].rt,t[pre].rt,mid+1,r,wz,fa);
}

inline void change(int k,int l,int r,int wz){
	if (l==r) return (void)(++t[k].d);
	if (wz<=mid) change(t[k].lt,l,mid,wz);
	else change(t[k].rt,mid+1,r,wz);
}

inline int get_ans(int k,int l,int r,int wz){
	if (l==r) return t[k].w;
	if (wz<=mid) return get_ans(t[k].lt,l,mid,wz);
	return get_ans(t[k].rt,mid+1,r,wz);
}

inline int find(int x){
	int l=1,r=len,ret=0;
	while (l<=r)
		if (ww[mid]<x) r=mid-1;
		else ret=mid,l=mid+1;
	return ret;
}

int main(void){
	for (read(ti); ti; --ti){
		read(n),read(m),num=0,memset(h,0,sizeof h);
		for (int i=1; i<=m; ++i){
			read(x),read(y),read(w1),read(w2);
			add(x,y,w1),e[i]=(note){x,y,w2},ww[i]=w2;
		}
		dij(),sort(e+1,e+1+m),sort(ww+1,ww+1+m,cmp),len=unique(ww+1,ww+1+m)-(ww+1);
		memset(root,0,sizeof root),size=0,build(root[0],1,n),now=0;
		for (int i=1; i<=m; ++i){
			if (e[i].w2!=e[i-1].w2) ++now,root[now]=root[now-1];
			int fx=gf(root[now],e[i].x),fy=gf(root[now],e[i].y);
			if (t[fx].f==t[fy].f) continue;
			if (t[fx].d>t[fy].d) swap(fx,fy);
			if (t[fy].w>t[fx].w) change_w(root[now],root[now],1,n,t[fy].f,t[fx].w);
			updata(root[now],root[now],1,n,t[fx].f,t[fy].f);
			if (t[fx].d==t[fy].d) change(root[now],1,n,t[fy].f);
		}
		read(Q),read(K),read(S),++S,ans=0;
		while (Q--){
			read(x),read(y),x=(x+K*ans-1)%n+1,y=(y+K*ans)%S,++y,y=find(y);
			printf("%d\n",ans=get_ans(root[y],1,n,t[gf(root[y],x)].f));
		}
	}
	return 0;
}

评测结果