代码

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
int n,m,cnt,q,k,s,t;
long long lastans;
struct edge2{
	int v,w;
};
struct node{
	bool b;
	std::vector<edge2>v;
}a[200005];
struct node2{
	int p,pp,zis;
    long long dis,xxx;
    int f[25];
}aa[400005];
struct edge{
	int u,v,w;
}e[400005];
struct eeee{
	int id;
    long long dis;
	bool operator >(const eeee& zyh)const{
		return dis>zyh.dis;
	}
};
std::priority_queue<eeee,std::vector<eeee>,std::greater<eeee> >pq;
void ddd(){
	while(pq.size())pq.pop();
	pq.push({1,0});
	aa[1].dis=0;
	for(int i=2;i<=n;i++)aa[i].dis=1e9;
	while(pq.size()){
		int now=pq.top().id;pq.pop();
		if(a[now].b)continue;
		a[now].b=1;
		for(edge2 v:a[now].v)if(aa[v.v].dis>aa[now].dis+v.w){
			aa[v.v].dis=aa[now].dis+v.w;
			pq.push({v.v,aa[v.v].dis});
		}
	}
}
bool cmp(edge a,edge b){
	return a.w>b.w;
}
int qu(int now){
    if(aa[now].pp==now)return now;
    aa[now].pp=qu(aa[now].pp);
    return aa[now].pp;
}
int main(){
//	freopen("return4.in","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) a[i].v.clear(),a[i].b=0;
		for(int i=1;i<=m;i++){
			int u,v,l,aaa;
			scanf("%d%d%d%d",&u,&v,&l,&aaa);
			e[i]={u,v,aaa};
			a[u].v.push_back({v,l});
			a[v].v.push_back({u,l});
		}
		ddd();
		std::sort(e+1,e+m+1,cmp);
    	for(int i=1;i<=n;i++)aa[i].p=aa[i].pp=i,aa[i].xxx=aa[i].dis,aa[i].zis=0;
    	cnt=n;
		for(int i=1;i<=m;i++){
			int pa=qu(e[i].u),pb=qu(e[i].v);
    	    if(pa==pb)continue;++cnt;
    	    aa[pa].p=aa[pa].pp=aa[pb].p=aa[pb].pp=aa[cnt].p=aa[cnt].pp=cnt;
    	    aa[cnt].xxx=std::min(aa[pb].xxx,aa[pa].xxx);
    	    aa[cnt].zis=e[i].w;//printf("(%d,%d,%d %d)",cnt,pa,pb,aa[cnt].zis);
		}
    	scanf("%d%d%d",&q,&k,&s);
    	for(int now=cnt;now;now--){
    		aa[now].f[0]=aa[now].p;
    		for(int i=1;i<25;i++)aa[now].f[i]=aa[aa[now].f[i-1]].f[i-1];
		}
		lastans=0;
    	while(q--){
    	    int v0,p0;
    	    scanf("%d%d",&v0,&p0);
    	    v0=((v0+k*lastans-1)%n)+1;
    	    p0=(p0+k*lastans)%(s+1);//printf("%d ",p0);
    	    for(int i=24;~i;i--)if(aa[aa[v0].f[i]].zis>p0&&aa[v0].f[i])v0=aa[v0].f[i];
    	    lastans=aa[v0].xxx;
    	    printf("%lld\n",lastans);
    	}
	}
	
}

评测结果