代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define ll long long
#define P pair<ll,ll>
#define mp make_pair
#define fi first
#define se second
#define N 400100
using namespace std;

ll n,m,T,faz[N],tt,d[N],fa[N][20],h[N],Q,K,S,last;
P tmp;
struct Bn
{
	ll u,v,a;
	bool operator < (const Bn &u) const
	{
		return a>u.a;
	}
}bn[N];
priority_queue<P,vector<P>,greater<P> >pq;
vector<P>to[N];

ll ff(ll u){return u==faz[u]?u:faz[u]=ff(faz[u]);}
inline ll find(ll u,ll v)
{
	ll i,t;
	for(i=19;i>=0;i--)
	{
		t=fa[u][i];
		if(h[t]>v) u=t;
	}
	return u;
}

int main()
{
	ll i,j,p,q,t;
	cin>>T;
	while(T--)
	{
		last=0;
		memset(d,0x3f,sizeof(d));
		memset(fa,0,sizeof(fa));
		scanf("%lld%lld",&n,&m);
		tt=n;
		for(i=1;i<2*n;i++) faz[i]=i;
		for(i=1;i<=m;i++)
		{
			scanf("%lld%lld%lld%lld",&bn[i].u,&bn[i].v,&t,&bn[i].a);
			to[bn[i].u].push_back(mp(bn[i].v,t));
			to[bn[i].v].push_back(mp(bn[i].u,t));
		}
		d[1]=0;
		pq.push(mp(0,1));
		for(;!pq.empty();)
		{
			tmp=pq.top();
			pq.pop();
			p=tmp.fi,q=tmp.se;
			if(d[q]<p) continue;
			for(i=0;i<to[q].size();i++)
			{
				t=to[q][i].fi;
				if(p+to[q][i].se>=d[t]) continue;
				d[t]=p+to[q][i].se;
				pq.push(mp(d[t],t));
			}
		}
//		for(i=1;i<=n;i++) cout<<d[i]<<" ";puts("");
		
		sort(bn+1,bn+m+1);
		for(i=1;i<=m;i++)
		{
			p=ff(bn[i].u),q=ff(bn[i].v);
			if(p==q) continue;
			tt++;
			h[tt]=bn[i].a;
			d[tt]=min(d[p],d[q]);
			fa[p][0]=fa[q][0]=tt;
			faz[p]=faz[q]=tt;
//			cout<<" "<<tt<<" "<<p<<endl<<" "<<tt<<" "<<q<<endl;
		}
		for(i=1;(1 << i)<=tt;i++)
		{
			for(j=1;j<=tt;j++)
			{
				fa[j][i]=fa[fa[j][i-1]][i-1];
			}
		}
//		for(i=1;i<=tt;i++) cout<<fa[i][1]<<" ";puts("");
		
		scanf("%lld%lld%lld",&Q,&K,&S);
		for(i=1;i<=Q;i++)
		{
			scanf("%lld%lld",&p,&q);
			p=(p+K*last-1)%n+1;
			q=(q+K*last)%(S+1);
			p=find(p,q);
			printf("%lld\n",d[p]);
			last=d[p];
		}
		
		for(i=1;i<=n;i++) to[i].clear();
	}
}

评测结果