代码

#pragma GCC optimize("-std=c++14")
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=2e5+505,maxm=4e5+505;
#define inf 0x3f3f3f3f
//最短路
int head[maxn],num_edge;
struct Edge{int next,to,v;};
Edge /*):*/ed[maxm*2];//:( && TAT
void add_edge(int from,int to,int v){
	ed[++num_edge].next=head[from];
	ed[num_edge].to=to;
	ed[num_edge].v=v;
	head[from]=num_edge;
}
#define pii pair<int,int>
int d[maxn];
priority_queue<pii,vector<pii>,greater<pii> >q;
#define fst first
#define sec second
void Dj(int s){
	memset(d,0x3f,sizeof(d));
	d[s]=0,q.push(pii(0,s));
	while(!q.empty()){
		pii h=q.top();q.pop();
		int k=h.second;
		if(h.first!=d[k])continue;
		for(int i=head[k];i;i=ed[i].next){
			int to=ed[i].to,e=d[k]+ed[i].v;
			if(d[to]>e){
				d[to]=e;
				q.push(pii(e,to));
			}
		}
	}
}

namespace ufs{
	int f[maxn],hst[maxn],size[maxn];//,_min[maxn];
	vector<pii>c[maxn];
	inline void init(int n)
		{for(int i=1;i<=n;i++)f[i]=i,hst[i]=0,size[i]=1,c[i].clear();}
	int find(int r,int h=0){
		if(f[r]==r)return r;
		if(hst[r]<=h)return r;
		return find(f[r],h);
	}
	bool unite(int x,int y,int dis){
		int fx=find(x),fy=find(y);
		if(fx==fy)return 0;
		if(size[fx]<size[fy])swap(fx,fy);
		f[fy]=fx;size[fx]+=fy;
//		int mn=c[fy].back();
//		if(!c[fx].empty())mn=min(mn,c[fx].back().sec);
		c[fx].push_back(pii(dis,min(c[fx].back().sec,c[fy].back().sec)));
		hst[fy]=dis;
		return 1;
	}
}

struct EDED{int u,v,l,a;}edge[maxm];
bool cmp(EDED a,EDED b){return a.a>b.a;}
#define cl(a) memset(a,0,sizeof(a))
int bound(auto b,auto e,int h){//C++14(luogu)
	auto ar=b;int l=0,r=e-b-1;
	//for(int i=l;i<=r;i++)cout<<ar[i].sec<<' ';cout<<'|'<<h<<"|\n";
	while(l<r){
		int mid=(l+r)/2+1;//cout<<mid<<";";
		if(ar[mid].fst<=h)r=mid-1;
		else l=mid;
	}//cout<<"LR:"<<l<<' '<<r<<endl;
	return ar[l].sec;
}
int work(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		EDED&ee=edge[i];
		scanf("%d%d%d%d",&ee.u,&ee.v,&ee.l,&ee.a);
		add_edge(ee.u,ee.v,ee.l);
		add_edge(ee.v,ee.u,ee.l);
	}
	Dj(1);
	
	sort(edge+1,edge+m+1,cmp);
	ufs::init(n);
	for(int i=1;i<=n;i++)ufs::c[i].push_back(pii(inf,d[i]));//ufs::_min[i]=d[i];
	
	for(int i=1;i<=m;i++){
		ufs::unite(edge[i].u,edge[i].v,edge[i].a);
	}
	
	int q,k,s,lastans=0;
	scanf("%d%d%d",&q,&k,&s);
	for(int i=1;i<=q;i++){
		int v0,p0;
		scanf("%d%d",&v0,&p0);
		int v=(v0+k*lastans-1)%n+1;
		int p=(p0+k*lastans)%(s+1);
		int fv=ufs::find(v,p);//cout<<fv<<endl;
		lastans=bound(ufs::c[fv].begin(),ufs::c[fv].end(),p);
		printf("%d\n",lastans);
	}
	//for(int i=1;i<=n;i++)cout<<ufs::f[i]<<' ';cout<<endl;
	//for(int i=1;i<=n;i++)cout<<d[i]<<' ';//ufs::hst[i]<<' ';
	cl(head),cl(ed),num_edge=0,cl(d);
	return 0;
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--)work();
}

评测结果