代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct o{
	int a,b,c;
}l[400000];
bool cmp(o a,o b){
	return a.c>b.c;
}
int t,n,m,a,b,c,d[400000],v[400001],ff[400000],s[400000],k[400000],f[20][400000],r,p,ans,z;
vector<int>e[400000],w[400000],g[400000];
priority_queue<pair<int,int>>q;
int find(int x){
	if(ff[x]==x){
		return x;
	}
	ff[x]=find(ff[x]);
	return ff[x];
}
void dfs(int x,int fa){
	f[0][x]=fa;
	d[x]=d[fa]+1;
	for(int i=0;i<g[x].size();i++){
		int y=g[x][i];
		dfs(y,x);
		k[x]=min(k[x],k[y]);
	}
}
signed main(){
	cin>>t;
	while(t--){
		ans=0;
		cin>>n>>m;
		z=n+1;
		for(int i=1;i<n*2;i++){
			f[0][i]=v[i]=s[i]=d[i]=0;
			k[i]=99999999999999999;
			e[i].clear();
			w[i].clear();
			g[i].clear();
			ff[i]=i;
		}
		for(int i=0;i<m;i++){
			scanf("%lld%lld%lld",&a,&b,&c);
			e[a].push_back(b);
			e[b].push_back(a);
			w[a].push_back(c);
			w[b].push_back(c);
			scanf("%lld",&c);
			l[i].a=a;
			l[i].b=b;
			l[i].c=c;
		}
		sort(l,l+m,cmp);
		for(int i=0;i<m;i++){
			a=l[i].a;
			b=l[i].b;
			c=l[i].c;
			if(find(a)!=find(b)){
				g[z].push_back(find(a));
				g[z].push_back(find(b));
				ff[find(a)]=z;
				ff[find(b)]=z;
				s[z]=c;
				z++;
			}
		}
		k[1]=0;
		q.push({0,1});
		while(!q.empty()){
			int x=q.top().second;
			q.pop();
			if(v[x]){
				continue;
			}
			v[x]=1;
			for(int i=0;i<e[x].size();i++){
				int y=e[x][i];
				if(k[x]+w[x][i]<k[y]){
					k[y]=k[x]+w[x][i];
					if(!v[y]){
						q.push({-k[y],y});
					}
				}
			}
		}
		dfs(z-1,0);
		for(int i=1;i<20;i++){
			for(int j=1;j<n*2;j++){
				f[i][j]=f[i-1][f[i-1][j]];
			}
		}
		cin>>m>>r>>p;
		while(m--){
			scanf("%lld%lld",&a,&b);
			a=(a+r*ans-1)%n+1;
			b=(b+r*ans)%(p+1);
			for(int i=19;i>=0;i--){
				if(f[i][a]&&s[f[i][a]]>b){
					a=f[i][a];
				}
			}
			ans=k[a];
			printf("%lld\n",ans);
		}
	}
	return 0;
}
//(☆▽☆)

评测结果