代码

#include<cstdio>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<vector>
#include<queue>
#include<bitset>
#include<stack>
#include<cassert>
#include<cctype>
// #include<iostream>
#define F first
#define S second
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
#define mem(x,y) memset(x,y,sizeof x)
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef double db;
const int INF=2e9;
const db eps=1e-12;
template<typename T>
inline void read(T &x)
{
	x=0; int f=1; char ch=getchar();
	while( (ch<'0' || ch>'9') && ch!='-') ch=getchar(); if(ch=='-') {f=-1; ch=getchar();}
	while(ch>='0' && ch <='9') x=x*10+ch-'0',ch=getchar();
	x*=f;
}
//==========================head template==========================
const int N=200010,M=400010,QQ=400010;
int n,m,K,Q,S;
struct Edge {
	int x,y,len,h,id;
	inline void in() {
		read(x); read(y); read(len); read(h);
	}
	bool operator < (const Edge &a)const {
		return h>a.h;
	}
}e[M];
int head[N],nxt[M<<1],to[M<<1],co[M<<1],h[M<<1],lst=1;
inline void adde(int x,int y,int c,int lim) {
	nxt[++lst]=head[x]; to[lst]=y; co[lst]=c; h[lst]=lim; head[x]=lst;
}
inline void add(int x,int y,int c,int h) {
	adde(x,y,c,h); adde(y,x,c,h);
}
bool used[N];
int dis[N];
priority_queue<pii,vector<pii>,greater<pii> > pq;
inline void Dij() {
	mem(used,0); mem(dis,63); dis[1]=0; pq.push(mp(0,1));
	while(!pq.empty()) {
		int u=pq.top().S; pq.pop();
		if(used[u]) continue; used[u]=1;
		for(int i=head[u];i;i=nxt[i]) {
			int v=to[i];
			if(!used[v] && dis[v]>dis[u]+co[i]) {
				dis[v]=dis[u]+co[i];
				pq.push(mp(dis[v],v));
			}
		}
	}
}
int que[N],he=1,ta=0;
int fat[N];
int father(int x) {return x==fat[x] ? x : fat[x]=father(fat[x]);}
const int ALL=N<<1,lgA=ceil(log2(ALL));
int val[ALL],lim[ALL],fa[ALL],anc[ALL][lgA+2],bel[ALL],ch[ALL][2],ind;
inline void Init() {
	for(int j=1;j<=lgA;j++)
		for(int i=1;i<=ind;i++)
			anc[i][j]=anc[anc[i][j-1]][j-1];
}
inline void Build() {
	for(int i=1;i<=n;i++) {fat[i]=i; bel[i]=i; val[i]=dis[i]; lim[i]=INF;}
	sort(e+1,e+m+1);
	ind=n;
	for(int i=1;i<=m;i++) {
		int fx=father(e[i].x),fy=father(e[i].y);
		if(fx!=fy) {
			// puts("?");
			int bx=bel[fx],by=bel[fy];
			anc[bx][0]=++ind;
			anc[by][0]=ind;
			fa[bx]=fa[by]=ind;
			val[ind]=min(val[bx],val[by]);
			lim[ind]=e[i].h;
			ch[ind][0]=bx; ch[ind][1]=by;
			bel[fy]=ind; fat[fx]=fy;
		}
	}
	Init();
}
inline int Work(int u,int l) {
	for(int i=lgA;i>=0;i--) if(lim[anc[u][i]]>l) {u=anc[u][i];}
	return val[u];
}
signed main()
{
	// freopen("return5.in","r",stdin);
	// freopen("my.out","w",stdout);
	int T; read(T);
	int lans=0;
	while(T--) {
		lans=0;
		read(n); read(m); lst=1; mem(head,0);
		for(int i=1;i<=m;i++) {
			e[i].in();
			add(e[i].x,e[i].y,e[i].len,e[i].h);
			e[i].id=i;
		}
		Dij();
		Build();
		read(Q); read(K); read(S);
		for(int i=1;i<=Q;i++) {
			int v,p; read(v); read(p);
			v=(v+1ll*K*lans-1)%n+1;
			p=(p+1ll*K*lans)%(S+1);
			// printf("%d %d\n",v,p);
			lans=Work(v,p);
			printf("%d\n",lans);
		}
		// cerr<<clock()<<endl;
	}
	return 0;
}
/*
2
5 5
1 2 1 2
2 3 1 2
4 3 1 2
5 3 1 2
1 5 2 1
4 1 3
5 1
5 2
2 0
4 0
5 5
1 2 1 2
2 3 1 2
4 3 1 2
5 3 1 2
1 5 2 1
4 1 3
5 1
5 2
2 0
4 0
*/

评测结果