代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>

#define fo(i,j,l) for(int i=j;i<=l;++i)
#define fd(i,j,l) for(int i=j;i>=l;--i)

using namespace std;
typedef long long ll;
const ll N=21e4,M=N<<2,K=N<<1,zd=(ll)5e9;

int n,m,oo,Q,KK,S,T;
int dfn[K],xl[K],en[K];

int ne[M],la[N],lb[M],len[M];
ll dis[N];

int f[K][19],fi[K],high[K];
int fa[K],lson[K],rson[K],d[K],dq[K];
ll tr[N<<3];

struct Comp{
	bool operator()(int a,int b)
	{return dis[a]!=dis[b]?dis[a]<dis[b]:a<b;}
};

set<int,Comp> ss;

struct note{
	int a,b,c;
}s[N*5];

inline int read()
{
	int o=0; char ch=' ';
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';ch=getchar())o=o*10+(ch^48);
	return o;
}

inline void llb(int a,int b,int c)
{ne[++oo]=la[a]; la[a]=oo; lb[oo]=b; len[oo]=c;}

inline void dij()
{
	dis[1]=0;
	ss.clear(); 
	ss.insert(1);
	fo(i,2,n)dis[i]=zd;
	fo(i,2,n)ss.insert(i); 
	while(!ss.empty()){
		int k=*ss.begin();
		ss.erase(k);
		for(int y=la[k];y;y=ne[y])
		if(dis[k]+len[y]<dis[lb[y]]){
			ss.erase(lb[y]);
			dis[lb[y]]=dis[k]+len[y];
			ss.insert(lb[y]);
		}
	}
}

inline ll min(ll a,ll b)
{return a<b?a:b;}

inline void build(int o,int l,int r)
{
	if(l==r){
		tr[o]=xl[l]>n?zd:dis[xl[l]];
		return;
	}
	int mid=l+r>>1;
	build(o<<1,l,mid); build((o<<1)^1,mid+1,r);
	tr[o]=min(tr[o<<1],tr[(o<<1)^1]);
}

inline ll ask(int o,int l,int r,int le,int ri)
{
	if(l==le&&r==ri)return tr[o];
	int mid=l+r>>1;
	if(ri<=mid)return ask(o<<1,l,mid,le,ri);
	else if(le>mid)return ask((o<<1)^1,mid+1,r,le,ri);
	else return min(ask(o<<1,l,mid,le,mid),ask((o<<1)^1,mid+1,r,mid+1,ri));
}

inline int getfa(int a)
{return (fi[a]==a)?a:(fi[a]=getfa(fi[a]));}

bool kmp(note a,note b)
{return a.c>b.c;}

inline void pri(ll o)
{
	if(!o)return;
	pri(o/10); putchar('0'+o%10);
}

int main()
{
	scanf("%d",&T);
	fo(tt,1,T){
		scanf("%d%d",&n,&m);
		fo(i,1,n*2)fo(l,0,18)f[i][l]=0;
		fo(i,1,2*n)dq[i]=0;
		fo(i,1,n)lson[i]=rson[i]=0;
		fo(i,1,n)la[i]=0; oo=0;
		ll sx=0; int h;
		fo(i,1,m){
			s[i].a=read();  s[i].b=read(); h=read(); s[i].c=read();
			llb(s[i].a,s[i].b,h); llb(s[i].b,s[i].a,h);
		}
		dij();
		sort(s+1,s+m+1,kmp);
		int k=n;
		fo(i,1,n)fi[i]=i,lson[i]=rson[i]=fa[i]=0;
		fo(i,1,m)if(getfa(s[i].a)!=getfa(s[i].b)){
			int a=fi[s[i].a],b=fi[s[i].b];
			fa[a]=fi[a]=fa[b]=fi[b]=++k;
			fi[k]=k;
			high[k]=s[i].c;
			lson[k]=a; rson[k]=b;
		}
		oo=0; int root;
		fo(i,1,k)if(!fa[i]){
			root=i; break;
		}
		int top=1; d[1]=root;
		while(top){
			int o=d[top];
			if(!dq[o]){
				dfn[o]=en[o]=++oo; xl[oo]=o;
				if(fa[o]){
					f[o][0]=fa[o];
					for(int l=0;f[f[o][l]][l];)f[o][l+1]=f[f[o][l]][l],++l;
				}
			}
			if(dq[o]==2)en[o]=en[rson[o]];
			if(!lson[o])dq[o]=2;
			dq[o]++;
			if(dq[o]==3)--top;
			else if(dq[o]==1)d[++top]=lson[o];
			else d[++top]=rson[o];
		}
		build(1,1,k);
		scanf("%d%d%d",&Q,&KK,&S);
		ll lastans=0; high[0]=-10000;
		fo(i,1,Q){
			int v=read(),p=read();
			v=(v+KK*lastans-1)%n+1;  p=(p+KK*lastans)%(S+1);
			for(int l=18;l>=0;--l)if(high[f[v][l]]>p)v=f[v][l];
			lastans=ask(1,1,k,dfn[v],en[v]);
			if(!lastans)puts("0");else pri(lastans),putchar('\n');
		}
	}
	return 0;
}

评测结果