代码

//#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<assert.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define fd(i,b,a) for(int i=(b);i>=(a);--i)
#define efo(i,v,u) for(int i=BB[v],u=B[BB[v]].to;i;u=B[i=B[i].nxt].to)
#define mset(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
int read(){int n=0,p=1;char ch;for(ch=getchar();ch<'0' || ch>'9';ch=getchar())if(ch=='-') p=-1;for(;'0'<=ch && ch<='9';ch=getchar()) n=n*10+ch-'0';return n*p;}
const int N=2e5+5,M=4e5+5,Q=4e5+5;
int n,m,B0,BB[N];
struct edge
{
	int to,nxt,l,h;
}B[M<<1];
struct Edge
{
	int x,y,l,h;
}b[M];
bool cmph(Edge a,Edge b){return a.h>b.h;}
void link(int u,int v,int l,int h)
{
	B[++B0].to=v,B[B0].nxt=BB[u],B[B0].l=l,B[B0].h=h,BB[u]=B0;
}
ll dis[N];
struct node
{
	int x;ll d;
	friend bool operator < (node a,node b){return a.d>b.d;}
};
priority_queue<node> q;
void dij()
{
	mset(dis,60);
	q.push((node){1,dis[1]=0});
	while(!q.empty())
	{
		node now=q.top();q.pop();
		int u=now.x;ll d=now.d;
		if(d>dis[u]) continue;
		efo(i,u,v)
			if(dis[u]+B[i].l<dis[v]) q.push((node){v,dis[v]=dis[u]+B[i].l});
	}
}
const int V=2e7+5;//attention!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
int tot,root[M],ls[V],rs[V],tr[V][3];//0->fa 1->rk 2->set_min_val
void build(int &v,int l=1,int r=n)
{
	if(!v) v=++tot;
	if(l==r)
	{
		tr[v][0]=l,tr[v][1]=0,tr[v][2]=dis[l];
		return;
	}
	int mid=(l+r)>>1;
	build(ls[v],l,mid);
	build(rs[v],mid+1,r);
}
int ID(int v,int x,int l=1,int r=n)
{
	if(l==r) return v;
	int mid=(l+r)>>1;
	return (x<=mid)?ID(ls[v],x,l,mid):ID(rs[v],x,mid+1,r);
}
void change(int u,int &v,int x,int z,int y,int l=1,int r=n)
{
	bool flag=0;
	if(!v || v==u)
	{
		v=++tot,flag=1;
		fo(k,0,2) tr[v][k]=tr[u][k];
	}
	if(l==r)
	{
		tr[v][z]=y;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
	{
		if(flag) rs[v]=rs[u];
		change(ls[u],ls[v],x,z,y,l,mid);
	}
	else
	{
		if(flag) ls[v]=ls[u];
		change(rs[u],rs[v],x,z,y,mid+1,r);
	}
}
int getfa(int t,int v)
{
	int q=ID(root[t],v);
	int f=tr[ID(root[t],v)][0];
	if(f==v) return v;
	return getfa(t,f);
}
int main()
{
	freopen("return.in","r",stdin);
	freopen("return.out","w",stdout);
	for(int cas=read();cas;cas--)
	{
		n=read(),m=read();
		B0=0;mset(BB,0);
		fo(i,1,m)
		{
			int u=read(),v=read(),l=read(),h=read();if(u==v) continue;
			b[i]=(Edge){u,v,l,h};
			link(u,v,l,h),link(v,u,l,h);
		}
		dij();
		sort(b+1,b+m+1,cmph);
		b[0].h=2e9;
		//mset(ls,0);mset(rs,0);mset(tr,0);
		fo(i,1,tot) ls[i]=rs[i]=tr[i][0]=tr[i][1]=tr[i][2]=0;
		tot=0;
		mset(root,0);
		build(root[0]);
		fo(i,1,m)
		{
			int x=b[i].x,y=b[i].y;
			int fx=getfa(i-1,x),fy=getfa(i-1,y);
			if(fx==fy) {root[i]=root[i-1];continue;}
			int vx=ID(root[i-1],fx),vy=ID(root[i-1],fy);
			if(tr[vx][1]<tr[vy][1]) swap(x,y),swap(fx,fy),swap(vx,vy);
			change(root[i-1],root[i],fy,0,fx);
			change(root[i-1],root[i],fx,1,tr[vx][1]+1);
			if(tr[vy][2]<tr[vx][2]) change(root[i-1],root[i],fx,2,tr[vy][2]);
		}
		ll ans=0;
		int q=read(),jy=read(),H=read();
		for(int hjy=1;q;q--,++hjy)
		{
			int v=(read()+jy*ans-1)%n+1,p=(read()+jy*ans)%(H+1);
			int l=0,r=m+1;
			while(l<r-1)
			{
				int mid=(l+r)>>1;
				if(b[mid].h>p) l=mid;
				else r=mid;
			}
			int t=l;
			int fv=getfa(t,v);
			ans=tr[ID(root[t],fv)][2];
			printf("%lld\n",ans);
		}
	}
	return 0;
}

评测结果