代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define mset(a,b) memset(a,b,sizeof a)
#define mcpy(a,b) memcpy(a,b,sizeof b)
#define lb(x) ((x)&(-(x)))
#define xx first
#define yy second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define pii pair<int,int> 
#define inf 0x3f3f3f3f
#define M 600005
#define N 400005
using namespace std;
typedef long long ll;
inline int Read(){
	int r=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')r=r*10+c-48,c=getchar();
	return r;
}
inline void Output(int x){
	if(!x){putchar('0'),putchar(10);return;}
	char t[15];
	int tp=0;
	while(x)t[++tp]=x%10+48,x/=10;
	while(tp)putchar(t[tp]),tp--;
	putchar(10);
}
const int INF=0x7fffffff;
struct data{int u,v,c,a;bool operator <(const data& t)const{return a<t.a;}}b[N];
int n,m,val[N],fa[M],root,c[M][2],v[M],mi[M],f[M][19];
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
namespace init{
	struct edge{int n,t,c;}e[N<<1];
	int head[N],ecnt,d[N];
	bool vis[N];
	priority_queue<pii,vector<pii>,greater<pii> > Q;
	inline void add(int a,int b,int c){e[++ecnt]=(edge){head[a],b,c},head[a]=ecnt;}
	inline void main(){
		for(int i=1;i<=n;i++)head[i]=vis[i]=0;ecnt=0;
		for(int i=1;i<=m;i++)add(b[i].u,b[i].v,b[i].c),add(b[i].v,b[i].u,b[i].c);
		mset(d,0x7f),d[1]=0,Q.push(mp(0,1));
		while(!Q.empty()){
			int x=Q.top().yy;Q.pop();
			if(vis[x])continue;vis[x]=1;
			for(int i=head[x];i;i=e[i].n)if(d[e[i].t]>d[x]+e[i].c)
				d[e[i].t]=d[x]+e[i].c,Q.push(mp(d[e[i].t],e[i].t));
		}
		for(int i=1;i<=n;i++)val[i]=d[i];
	}
}
inline void dfs(int x){
	for(int i=1;i<19;i++)f[x][i]=f[f[x][i-1]][i-1];
	if(x<=n){mi[x]=val[x];return;}
	f[c[x][0]][0]=f[c[x][1]][0]=x;
	dfs(c[x][0]),dfs(c[x][1]);
	mi[x]=min(mi[c[x][0]],mi[c[x][1]]);
}
int main(){
	freopen("return.in","r",stdin);
	freopen("return.out","w",stdout);
	int T=Read();
	while(T--){
		n=Read(),m=Read();
		for(int i=1;i<=m;i++)b[i].u=Read(),b[i].v=Read(),b[i].c=Read(),b[i].a=Read();
		init::main();
		sort(b+1,b+1+m);
		for(int i=1;i<=n;i++)fa[i]=i;
		for(int i=m;i;i--){
			int x=find(b[i].u),y=find(b[i].v);
			if(x^y)fa[x]=fa[y]=fa[i+n]=i+n,c[i+n][0]=x,c[i+n][1]=y,root=i+n,v[i+n]=b[i].a;
		}
		f[root][0]=root,dfs(root);
		int Q,K,S,ans=0;Q=Read(),K=Read(),S=Read();
		while(Q--){
			int x,p;x=Read(),p=Read();
			x=(1ll*x+K*ans-1)%n+1;
			p=(1ll*p+K*ans)%(S+1);
			for(int i=18;~i;i--)if(v[f[x][i]]>p)x=f[x][i];
//			Output(ans=mi[x]);
			printf("%d\n",ans=mi[x]);
		}
	}	
	return 0;
}

评测结果