代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
int read(){
	char ch=getchar();
	int x=0;
	while (!('0'<=ch&&ch<='9'))
		ch=getchar();
	while ('0'<=ch&&ch<='9')
		x=(x<<1)+(x<<3)+ch-48,ch=getchar();
	return x;
}
const int N=200005,M=400005;
int T,n,m;
struct Gragh{
	int cnt,y[M*2],z[M*2],nxt[M*2],fst[N];
	void clear(){
		cnt=0;
		memset(fst,0,sizeof fst);
	}
	void add(int a,int b,int c){
		y[++cnt]=b,z[cnt]=c,nxt[cnt]=fst[a],fst[a]=cnt;
	}
}g;
struct Edge{
	int x,y,h;
	Edge(){}
	Edge(int _x,int _y,int _h){
		x=_x,y=_y,h=_h;
	}
	friend bool operator < (Edge a,Edge b){
		return a.h>b.h;
	}
}e[M];
int dis[N],vis[N];
struct Node{
	int x,d;
	Node(){}
	Node(int _x,int _d){
		x=_x,d=_d;
	}
	friend bool operator < (Node x,Node y){
		return x.d>y.d;
	}
};
priority_queue <Node> Q;
void Dijkstra(){
	while (!Q.empty())
		Q.pop();
	for (int i=1;i<=n;i++)
		dis[i]=2e9+5;
	dis[1]=0;
	memset(vis,0,sizeof vis);
	Q.push(Node(1,0));
	while (!Q.empty()){
		Node now=Q.top();
		Q.pop();
		int x=now.x;
		if (vis[x])
			continue;
		vis[x]=1,dis[x]=now.d;
		for (int i=g.fst[x];i;i=g.nxt[i])
			Q.push(Node(g.y[i],dis[x]+g.z[i]));
	}
}
const int N2=N*2;
int fa[N2],son[N2][2],h[N2],mindis[N2],Fa[N2][20];
int getf(int x){
	return fa[x]==x?x:fa[x]=getf(fa[x]);
}
int Qu[N2],head,tail;
int main(){
	T=read();
	while (T--){
		n=read(),m=read();
		g.clear();
		for (int i=1;i<=m;i++){
			int x=read(),y=read(),l=read(),a=read();
			g.add(x,y,l);
			g.add(y,x,l);
			e[i]=Edge(x,y,a);
		}
		Dijkstra();
		sort(e+1,e+m+1);
		memset(fa,0,sizeof fa);
		for (int i=1;i<=n*2;i++)
			fa[i]=i;
		for (int i=1;i<=n;i++)
			h[i]=e[1].h+1;
		int cnt=n;
		memset(son,0,sizeof son);
		memset(h,0,sizeof h);
		for (int i=1;i<=m;i++){
			int x=getf(e[i].x),y=getf(e[i].y);
			if (x==y)
				continue;
			h[++cnt]=e[i].h;
			son[cnt][0]=x,son[cnt][1]=y;
			fa[x]=fa[y]=cnt;
		}
		head=tail=0;
		Qu[++tail]=cnt;
		while (head<tail){
			int x=Qu[++head];
			for (int i=1;i<19;i++)
				Fa[x][i]=Fa[Fa[x][i-1]][i-1];
			for (int i=0;i<2;i++){
				int y=son[x][i];
				if (y){
					Fa[y][0]=x;
					Qu[++tail]=y;
				}
			}
		}
		for (int i=tail;i>0;i--){
			int x=Qu[i];
			if (x<=n)
				mindis[x]=dis[x];
			else
				mindis[x]=min(mindis[son[x][0]],mindis[son[x][1]]);
		}
		int q=read(),K=read(),S=read();
		int lastans=0;
		h[0]=-1;
		while (q--){
			int v=read(),p=read();
			v=(v+K*lastans-1)%n+1;
			p=(p+K*lastans)%(S+1);
			for (int i=18;i>=0;i--)
				if (h[Fa[v][i]]>p)
					v=Fa[v][i];
			printf("%d\n",lastans=mindis[v]);
		}
	}
	return 0;
}

评测结果