代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define fo(i,j,k) for(int i=j;i<=k;++i)
#define fd(i,j,k) for(int i=j;i>=k;--i)
#define rep(i,x) for(int i=ls[x];i;i=nx[i])
using namespace std;
const int N=2e5+10,M=8e5+10,inf=1e9;
typedef pair<int,int> par;
priority_queue<par,vector<par>,greater<par> >q;
int to[M],nx[M],ls[N<<1],vl[M],num=0;
void link(int u,int v,int w){
	to[++num]=v,nx[num]=ls[u],ls[u]=num;
	vl[num]=w;
}
void clear(){
	memset(ls,0,sizeof(ls)),num=0;
}
int read(){
    char ch=' ';int t=0;
    for(;ch<'0' || ch>'9';ch=getchar());
    for(;ch>='0' && ch<='9';ch=getchar()) t=(t<<1)+(t<<3)+ch-48;
	return t;
}
struct node{
	int u,v,l,a;
}e[M];
bool cmp(node x,node y) {return x.a<y.a;}
int d[N];
bool vis[N];
void dijstra(){
	memset(vis,0,sizeof(vis));
	memset(d,60,sizeof(d)),d[1]=0;
	q.push(make_pair(d[1],1));
	for(;;){
		int x=q.top().second;
		q.pop();
		vis[x]=1;
		rep(i,x){
			int v=to[i];
			if(vis[v]) continue;
			if(d[x]+vl[i]<d[v]){
				d[v]=d[x]+vl[i];
				q.push(make_pair(d[v],v));
			}
		}
		if(q.empty()) break;
	}
}
int f[N<<1],tot=0;
int find(int x){
	return !f[x]?x:f[x]=find(f[x]);
}
int n,m;
int fa[N<<1][20],g[N<<1][20];
int w[N<<1];
void pre(int x){
	fo(i,1,19){
		fa[x][i]=fa[fa[x][i-1]][i-1];
		g[x][i]=min(g[x][i-1],g[fa[x][i-1]][i-1]);
	}
	w[x]=x>n?inf:d[x];
	rep(i,x){
		int v=to[i];
		fa[v][0]=x,g[v][0]=vl[i];
		pre(v),w[x]=min(w[x],w[v]);
	}
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d %d",&n,&m);
		fo(i,1,m){
			node x;
			x.u=read(),x.v=read(),x.l=read(),x.a=read();
			link(x.u,x.v,x.l),link(x.v,x.u,x.l);
			e[i]=x;
		}
		dijstra();
		sort(e+1,e+m+1,cmp);
		clear();
		memset(f,0,sizeof(f)),tot=n;
		fd(i,m,1){
			int u=find(e[i].u),v=find(e[i].v);
			if(u!=v){
				tot++,f[u]=f[v]=tot;
				link(tot,u,e[i].a),link(tot,v,e[i].a);
			}
		}
		pre(tot);
		int Q=read(),K=read(),S=read();
		int ans=0;
		while(Q--){
			int x=(read()+K*ans-1)%n+1,p=(read()+K*ans)%(S+1);
			fd(i,19,0)
			if(fa[x][i] && g[x][i]>p) x=fa[x][i];
			printf("%d\n",ans=w[x]);
		}
		clear();
	}
}

评测结果