代码

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define gc getchar
#define pc putchar
#define mp make_pair
/*
inline
char get_char(){
	static char buf[1<<18|1],*p1=buf,*p2=buf;
	return p1==p2&&(p1=(p2=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++;
}
/*char buf[1<<18|1],*p1=buf,*p2=buf+(1<<18);
inline
void put_char(char c){
	*p1++=c;
	if(p1==p2)fwrite(buf,1,p1-buf,stdout),p1=buf;
}*/

inline
int getint(){
	int num=0;
	char c=gc();
	for(;!isdigit(c)&&c!=EOF;c=gc());
	if(c==EOF)return EOF;
	for(;isdigit(c);c=gc())num=(num<<1)+(num<<3)+(c^48);
	return num;
}

inline
void outint(int a){
	if(a>9)outint(a/10);
	pc((a-a/10*10)^48);
}

int T,n,m,Q,K,S,lasans,tot;
int Last[200002],nxt[800002],to[800002],w[800002],ecnt;
int First[400002],nx[400002],t[400002],cnt;
int dep[400002],h[400002];
int logn[400002],dist[400002],f[400002],fa[400002][20];
bool vis[200002];
struct _{int u,v,h;}E[400002];inline bool cmp(const _ &a,const _ &b){return a.h>b.h;}

inline
void addedge(int u,int v,int val){
	nxt[++ecnt]=Last[u],Last[u]=ecnt,to[ecnt]=v,w[ecnt]=val;
	nxt[++ecnt]=Last[v],Last[v]=ecnt,to[ecnt]=u,w[ecnt]=val; 
}

priority_queue<pair<int,int> ,vector<pair<int,int> > ,greater<pair<int,int> > > q;
inline
void dijkstra(){
	dist[1]=0;
	q.push(mp(0,1));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=true;
		for(int re e=Last[u],v=to[e];e;e=nxt[e],v=to[e]){
			if(dist[v]>dist[u]+w[e]){
				dist[v]=dist[u]+w[e];
				q.push(mp(dist[v],v));
			}
		}
	}
}

inline
void add(int u,int v){
	nx[++cnt]=First[u],First[u]=cnt,t[cnt]=v;
}

inline
void dfs(int u,int pa){
	dep[u]=dep[pa]+1;
	fa[u][0]=pa;
	for(int re i=1;i<=logn[dep[u]];++i)fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int re e=First[u],v=t[e];e;e=nx[e],v=t[e])
	dfs(v,u),dist[u]=min(dist[u],dist[v]);
}

inline int getfa(int x){return f[x]==x?x:(f[x]=getfa(f[x]));}

inline
void kruskal(){
	sort(E+1,E+1+m,cmp);
	for(int re i=1;i<=m;++i){
		int x=getfa(E[i].u),y=getfa(E[i].v);
		if(x!=y){
			add(++tot,x);
			add(tot,y);
			f[x]=f[y]=tot;
			h[tot]=E[i].h;
			if(tot==n*2-1)break; 
		}
	}
	dfs(tot,0);
}

inline
int query(int v,int p){
	for(int re i=logn[dep[v]];i>=0;--i)if(h[fa[v][i]]>p)v=fa[v][i];
	return dist[v];
}

int main(){
	h[0]=-1;
	for(int re i=2;i<=400000;++i)logn[i]=logn[i>>1]+1;
	T=getint();
	while(T--){
		lasans=ecnt=cnt=0;
		memset(dep,0,sizeof dep);
		memset(vis,0,sizeof vis);
		memset(dist,0x3f,sizeof dist);
		memset(Last,0,sizeof Last);
		memset(First,0,sizeof First);
		memset(fa,0,sizeof fa);
		tot=n=getint();
		m=getint();
		for(int re i=1;i<=(n<<1);++i)f[i]=i;
		for(int re i=1;i<=m;++i)
		E[i].u=getint(),E[i].v=getint(),E[i].h=getint(),
		addedge(E[i].u,E[i].v,E[i].h),E[i].h=getint();
		dijkstra();
		kruskal();
		Q=getint();
		K=getint();
		S=getint();
		while(Q--){
			int v=(getint()+K*lasans-1)%n+1;
			int p=(getint()+K*lasans)%(S+1);
			outint(lasans=query(v,p));
			pc('\n'); 
		}
	}
//	fwrite(buf,1,p1-buf,stdout);
	return 0;
}

评测结果