代码

#include<bits/stdc++.h>
#define to edge[i].v
#define mp make_pair
#define rint register int
#define debug(x) cerr<<#x<<"="<<x<<endl
#define fgx cerr<<"-------------"<<endl
#define N 500000
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
char SS[3000000];
int tot,head[N],vis[N],b[N],sz; ll dis[N];
struct Edge{int v,w,next;Edge(int _v=0,int _w=0,int _n=0):v(_v),w(_w),next(_n){}}edge[1000000];
inline void add(int x,int y,int z){edge[++tot]=Edge(y,z,head[x]);head[x]=tot;}
struct E{int u,v,l,h;}e[N];
inline bool cmp(E x,E y){return x.h<y.h;}
struct node
{	int l,r,A;ll B;node *lc,*rc;
	node(int _l=0,int _r=0):l(_l),r(_r){lc=rc=NULL;A=B=0;}
}*rt[N],*a[N];
inline node *build(int l,int r)
{	node *x=new node(l,r);
	if(l==r){x->A=l;return x;}
	int mid=(l+r)>>1;
	x->lc=build(l,mid); x->rc=build(mid+1,r);
	return x;
}
inline node *BUILD(int l,int r)
{	node *x=new node(l,r);
	if(l==r){x->A=1;x->B=dis[l];return x;}
	int mid=(l+r)>>1;
	x->lc=BUILD(l,mid); x->rc=BUILD(mid+1,r);
	return x;
}
priority_queue<pii > q;
inline void dij(int n)
{	for(rint i=1;i<=n;i++) vis[i]=0,dis[i]=1e18;
	dis[1]=0; q.push(mp(0,1));
	while(!q.empty())
	{	int x=q.top().second; q.pop();
		if(vis[x]) continue; vis[x]=1;
		for(rint i=head[x];i;i=edge[i].next)
		if(dis[to]>dis[x]+edge[i].w) dis[to]=dis[x]+edge[i].w,q.push(mp(-dis[to],to));
	}
}
inline int q1(const node *x,int pos)
{//	if(TAG) debug(pos);
	if(x->l==x->r){return x->A;}
	int mid=(x->l+x->r)>>1;
	if(pos<=mid) return q1(x->lc,pos);
	else return q1(x->rc,pos);
}
inline ll q2(const node *x,int pos)
{	if(x->l==x->r) return x->B;
	int mid=(x->l+x->r)>>1;
	if(pos<=mid) return q2(x->lc,pos);
	else return q2(x->rc,pos);
}
inline node *ins1(const node *la,int pos,int k)
{	node *x=new node(la->l,la->r); x->lc=la->lc; x->rc=la->rc;
	if(x->l==x->r){x->A=k;return x;}
	int mid=(x->l+x->r)>>1;
	if(pos<=mid) x->lc=ins1(la->lc,pos,k);
	else x->rc=ins1(la->rc,pos,k);
	return x;
}
inline node *ins2(const node *la,int pos,int A,ll B)
{	node *x=new node(la->l,la->r); x->lc=la->lc; x->rc=la->rc; x->A=la->A; x->B=la->B;
	if(x->l==x->r){x->A+=A;x->B=min(x->B,B);return x;}
	int mid=(x->l+x->r)>>1;
	if(pos<=mid) x->lc=ins2(la->lc,pos,A,B);
	else x->rc=ins2(la->rc,pos,A,B);
	return x;
}
inline int findfa(const node *x,int y){for(int cur=0;((cur=q1(x,y))!=y);y=cur);return y;}
inline int read()
{   char c; int x=0; for(c=getchar();!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())x=x*10+(c^'0'); return x;
}
inline void pr(ll x)
{	if(!x) SS[++sz]='0';
	else
	{	char ch[20]; int p=0;
		for(;x;ch[++p]=x%10+'0',x/=10);
		for(rint i=p;i>=1;i--) SS[++sz]=ch[i];
	}
}
int main()
{	freopen("return.in","r",stdin);
	freopen("return.out","w",stdout);
	int t,t0=clock(); cin>>t;
	while(t--)
	{	tot=0; memset(head,0,sizeof(head));
		int n,m; scanf("%d%d",&n,&m);
		for(rint i=1;i<=m;i++)
		e[i].u=read(),e[i].v=read(),e[i].l=read(),e[i].h=read(),
		add(e[i].u,e[i].v,e[i].l),add(e[i].v,e[i].u,e[i].l),b[i]=e[i].h;
		dij(n); sort(e+1,e+m+1,cmp); sort(b+1,b+m+1);
		int len=unique(b+1,b+m+1)-b-1,p=m,id=len+1;
		rt[len+1]=build(1,n); a[len+1]=BUILD(1,n);
		for(rint i=len;i>=1;i--)
		for(;p>=1&&e[p].h==b[i];p--)
		{	int x=findfa(rt[id],e[p].u),y=findfa(rt[id],e[p].v);
			if(x!=y)
			{	int X=q1(a[id],x),Y=q1(a[id],y);
				if(X<Y) swap(x,y),swap(X,Y);
				rt[i]=ins1(rt[id],y,x); a[i]=ins2(a[id],x,Y,q2(a[id],y));
			}
			else rt[i]=rt[id],a[i]=a[id];
			id=i;
		}
		int q,K,S,la=0,v,P; q=read();K=read();S=read(); b[++len]=S+1;
		while(q--)
		{	v=read(),P=read(); v=(v+(ll)K*la-1)%n+1,P=(P+(ll)K*la)%(S+1);
			int k=upper_bound(b+1,b+len+1,P)-b;
			pr(la=q2(a[k],findfa(rt[k],v))); SS[++sz]='\n';
		}
	}
	fwrite(SS+1,sizeof(char),sz,stdout);
	return 0;
}

评测结果