代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct rec{
	int l,r,w;
	long long dist;
}edge[400005];
struct node{
	int to;
	long long w;
	node *next;
}*nd[200005];
int i,j,m,n,x,y,s,q,k,v0,p0,maxlog,u,test,ii,heapcnt;
long long lastans,inf,dist[200005],cnt;
int father[400005],fathermul[400005][20],minh[400005],mindist[400005];
bool visit[200005];
int heap[200005];
void addd(int u,int v,long long w){
	node *p=new node();
	p->to=v;
	p->w=w;
	p->next=nd[u];
	nd[u]=p;
}
long long getmin(long long a,long long b){
	if (a<b) return a;
	else return b;
}
bool cmp(rec a,rec b){
	if (a.w>b.w) return true;
	else return false;
}
void move(int u){
	int temp;
	if (u>1){
		if (dist[heap[u]]<dist[heap[u>>1]]){
			temp=heap[u];
			heap[u]=heap[u>>1];
			heap[u>>1]=temp;
			move(u>>1);
			return;
		}
	}
	if (u*2==heapcnt){
		if (dist[heap[u]]>dist[heap[u<<1]]){
			temp=heap[u];
			heap[u]=heap[u<<1];
			heap[u<<1]=temp;
		}
		return;
	}
	if (u*2+1<=heapcnt){
		int tt;
		if (dist[heap[u<<1]]<dist[heap[u<<1|1]]){
			tt=u<<1;
		}else{
			tt=u<<1|1;
		}
		if (dist[heap[u]]>dist[heap[tt]]){
			temp=heap[u];
			heap[u]=heap[tt];
			heap[tt]=temp;
			move(tt);
		}
	}
}
void dij(){
	heapcnt=1;
	heap[1]=1;
	int i,u;
	for(i=2;i<=n;i++){
		dist[i]=inf;
	}
	dist[1]=0;
	node *p;
	while(heapcnt){
		u=heap[1];
		heap[1]=heap[heapcnt];
		heapcnt--;
		if (heapcnt) move(1);
		p=nd[u];
		while(p){
			if (dist[u]+p->w<dist[p->to]){
				dist[p->to]=dist[u]+p->w;
				heapcnt++;
				heap[heapcnt]=p->to;
				move(heapcnt);
			}
			p=p->next;
		}
	}
}
int getfather(int u){
	if (u==father[u]) return u;
	father[u]=getfather(father[u]);
	return father[u];
}
int main(){
scanf("%d",&test);
while(test--){
	lastans=0;
	maxlog=19;
	inf=1000000000000000000;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		nd[i]=NULL;
	}
	for(i=1;i<=m;i++){
		scanf("%d%d%lld%d",&edge[i].l,&edge[i].r,&edge[i].dist,&edge[i].w);
		addd(edge[i].l,edge[i].r,edge[i].dist);
		addd(edge[i].r,edge[i].l,edge[i].dist);
	}
	dij();
	sort(edge+1,edge+m+1,cmp);
	for(i=1;i<=n;i++){
		father[i]=i;
		mindist[i]=dist[i];
	}
	cnt=n;
	for(i=1;i<=m;i++){
		x=getfather(edge[i].l);
		y=getfather(edge[i].r);
		if (x!=y){
			cnt++;
			father[cnt]=father[x]=father[y]=cnt;
			fathermul[x][0]=fathermul[y][0]=cnt;
			minh[cnt]=edge[i].w;
			mindist[cnt]=getmin(mindist[x],mindist[y]);//the minimum dist in the subtree of cnt;
		}
	}
	fathermul[cnt][0]=cnt;
	for(i=1;i<=maxlog;i++){
		for(j=1;j<=cnt;j++){
			fathermul[j][i]=fathermul[fathermul[j][i-1]][i-1];
		}
	}
	scanf("%d%d%d",&q,&k,&s);
	while(q--){
		scanf("%d%d",&v0,&p0);
		v0=(v0+k*lastans-1)%n+1;
		p0=(p0+k*lastans)%(s+1);
		u=v0;
		for(i=maxlog;i>=0;i--){
			if (minh[fathermul[u][i]]>p0){
				u=fathermul[u][i];
			}
		}
		lastans=mindist[u];
		printf("%lld\n",lastans);
	}
}
	return 0;
}

评测结果