代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int N=4e5+5,M=4e5+5;
constexpr long long INF{0x3F3F3F3F3F3F3F3Fll};
int n,m,q,kk,ss,ec,eh[N],nc;
int dep[N],w[N],fa[N][20];
long long dis[N],mn[N];
struct EI{int u,v,w;}ei[M];
struct{int nxt,to,dis,h;}e[M<<1];
struct{
	int fa[N];
	inline void init(int n){
		iota(fa+1,fa+n+1,1);
	}
	int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
	inline void merge(int x,int y){
		if((x=find(x))==(y=find(y))) return ;
		fa[x]=y;
	}
}dsu;
inline void adde(int u,int v,int w,int h){
	e[++ec]={eh[u],v,w,h},eh[u]=ec;
}
void dij(int s){
	using Q=pair<long long,int>;
	vector<bool> vst(n+5,false);
	priority_queue<Q,vector<Q>,greater<Q> > q;
	memset(dis,0x3f,sizeof dis);
	q.emplace(dis[s]=0,s);
	while(!q.empty()){
		int u{q.top().second}; q.pop();
		if(vst[u]) continue;
		vst[u]=true;
		for(int i{eh[u]};i;i=e[i].nxt){
			int v{e[i].to},w{e[i].dis};
			if(dis[u]+w<dis[v])
				q.emplace(dis[v]=dis[u]+w,v);
		}
	}
}
void krus(){
	nc=n;
	fill(w+1,w+nc+1,INF);
	memset(eh+1,0,n*sizeof(int)),ec=0;
	sort(ei+1,ei+m+1,[](const EI &a,const EI &b){return a.w>b.w;});
	dsu.init(n*2);
	for(int i{1};i<=m;++i){
		int u{ei[i].u},v{ei[i].v},w{ei[i].w};
		u=dsu.find(u),v=dsu.find(v);
		if(u!=v){
			int t{++nc};
			::w[t]=w;
			adde(t,u,0,0),adde(t,v,0,0);
			dsu.merge(u,t),dsu.merge(v,t);
		}
	}
}
void dfs(int u,int fa){
	for(int i{0};i<=20;++i) ::fa[u][0]=0;
	dep[u]=dep[::fa[u][0]=fa]+1;
	mn[u]=(u<=n)?dis[u]:INF;
	for(int i{1};i<=__lg(dep[u]);++i)
		::fa[u][i]=::fa[::fa[u][i-1]][i-1];
	for(int i{eh[u]};i;i=e[i].nxt){
		int v{e[i].to};
		if(v==fa) continue;
		dfs(v,u);
		mn[u]=min(mn[u],mn[v]);
	}
}
int findw(int u,int lim){
	for(int i{__lg(dep[u])};i>=0;--i){
		if(fa[u][i]&&w[fa[u][i]]>lim)
			u=fa[u][i];
	}
	return u;
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int tc; cin>>tc;
	while(tc--){
		cin>>n>>m;
		memset(fa,0,sizeof fa);
		memset(w,0,sizeof w);
		memset(eh+1,0,n*2*sizeof(int)),ec=nc=0;
		for(int i{1};i<=m;++i){
			int u,v,w,h; cin>>u>>v>>w>>h;
			ei[i]={u,v,h};
			adde(u,v,w,h);
			adde(v,u,w,h);
		}
		dij(1);
		krus();
		dfs(nc,0);
		cin>>q>>kk>>ss;
		long long lsta{0};
		while(q--){
			int s,p; cin>>s>>p;
			if(kk){
				s=int((s+lsta-1)%n+1);
				p=int((p+lsta)%(ss+1));
			}
			int u{findw(s,p)};
			cout<<(lsta=mn[u])<<'\n';
		}
	}
	return 0;
}

评测结果