代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
struct Edge {
	int to,next,value,height;
} e[800005],e3[800005];
struct Edge2 {
	int from,to,height;
	bool operator <(const Edge2 xx) const {
		return height>xx.height;
	}
} e2[400005];
struct Node {
	int num,dis;
	bool operator <(const Node xx) const {
		return dis>xx.dis;
	}
};
int n,m,q,K,S,h[400005],prt[400005],cnt,dis[400005],cnt3,h3[400005],p[400005][20],mindis[400005],val[400005];
void Add_Edge(int x,int y,int z,int w) {
	e[++cnt]=(Edge){y,h[x],z,w};
	h[x]=cnt;
}
void Add_Edge3(int x,int y) {
	e3[++cnt3]=(Edge){y,h3[x],0,0};
	h3[x]=cnt3;
}
void Dijkstra(int from) {
	priority_queue<Node> q;
	q.push((Node){from,0});
	for(int i=1; i<=n; i++)dis[i]=0x7fffffff;
	dis[from]=0;
	while(!q.empty()) {
		Node nnow=q.top();
		q.pop();
		if(dis[nnow.num]!=nnow.dis)continue;
		int now=nnow.num;
		for(int i=h[now]; i; i=e[i].next) {
			int y=e[i].to;
			if(dis[now]+e[i].value<dis[y]) {
				dis[y]=dis[now]+e[i].value;
				q.push((Node){y,dis[y]});
			}
		}
	}
}
int Getfa(int x) {
	return x==prt[x]?x:prt[x]=Getfa(prt[x]);
}
void MakeKruskal() {
	sort(e2+1,e2+m+1);
	for(int i=1; i<=n; i++)prt[i]=i;
	for(int i=1,tot=n; i<=m; i++) {
		int fx=Getfa(e2[i].from),fy=Getfa(e2[i].to);
		if(fx==fy)continue;
		prt[fx]=prt[fy]=++tot,prt[tot]=tot,val[tot]=e2[i].height;
		Add_Edge3(tot,fx);
		Add_Edge3(tot,fy);
	}
}
void DFS(int now,int fa) {
	p[now][0]=fa;
	for(int i=1; p[now][i-1]; i++)p[now][i]=p[p[now][i-1]][i-1];
	if(now<=n)mindis[now]=dis[now];
	else mindis[now]=0x7fffffff;
	for(int i=h3[now]; i; i=e3[i].next) {
		int y=e3[i].to;
		if(y==fa)continue;
		DFS(y,now);
		mindis[now]=min(mindis[now],mindis[y]);
	}
}
int main() {
//	freopen("testdata.in","r",stdin);
//	freopen("a.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--) {
		memset(h,0,sizeof(h));
		memset(h3,0,sizeof(h3));
		memset(val,0,sizeof(val));
		memset(p,0,sizeof(p));
		cnt=cnt3=0;
		scanf("%d%d",&n,&m);
		for(int i=1,x,y,z,w; i<=m; i++) {
			scanf("%d%d%d%d",&x,&y,&z,&w);
			Add_Edge(x,y,z,w),Add_Edge(y,x,z,w);
			e2[i]=(Edge2){x,y,w};
		}
		Dijkstra(1);
		MakeKruskal();
		DFS(2*n-1,0);
		scanf("%d%d%d",&q,&K,&S);
		for(int i=1,lastans=0,v,pp,md=log2(n); i<=q; i++) {
			scanf("%d%d",&v,&pp);
			v=(v+lastans*K-1)%n+1,pp=(pp+lastans*K)%(S+1);
			for(int j=md; j>=0; j--)if(val[p[v][j]]>pp)v=p[v][j];
			printf("%d\n",lastans=mindis[v]);
		}
	}
	return 0;
}

评测结果