代码

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 500005
#define inf 0x3f3f3f3f
using namespace std;

namespace Struct{
	struct temp{
		int x,y;
		bool operator<(const temp& o)const{return y>o.y;}
		temp(int a,int b){x=a,y=b;}
	};
	struct Edge{
		int v,c,nxt;
		Edge(){}
		Edge(int _v,int _n,int _c){v=_v,nxt=_n,c=_c;}
	};
	Edge e[N<<1];int head[N],tot;
	void AddEdge(int u,int v,int c){
		e[++tot]=Edge(v,head[u],c);head[u]=tot;
		e[++tot]=Edge(u,head[v],c);head[v]=tot;
	}
	struct edge{
		int u,v,c,l;
		edge(){}void init(){
			scanf("%d%d%d%d",&u,&v,&c,&l);
			AddEdge(u,v,c);
		}
		edge(int a,int b,int w,int h){u=a,v=b,c=w,l=h;}
		bool operator<(const edge& o)const{return l>o.l;}
	};
}using namespace Struct;
namespace Graph{
	int n,m;
	edge E[N];
	int dis[N];	
	void clear(){
		memset(dis,0x3f,sizeof dis);
		tot=0;memset(head,0,sizeof head);
	}
	void Dijkstra(int s){
		priority_queue<temp>q;
		dis[s]=0;q.push(temp(s,0));
		int top;
		while (!q.empty()){
			top=q.top().x;q.pop();
			for (int i=head[top];i;i=e[i].nxt){
				if(dis[e[i].v]>dis[top]+e[i].c)
					dis[e[i].v]=dis[top]+e[i].c,
					q.push(temp(e[i].v,dis[e[i].v]));
			}
		}
	}
}
namespace Deal{
	using namespace Graph;
	int fa[N],cnt,mi[N];
	int g[N][21],f[N][21],ch[N][2];
	int find(int x){
		return fa[x]==x?x:fa[x]=find(fa[x]);
	}
	int dfs(int x){
		mi[x]=inf;
		if (x<=n)return mi[x]=dis[x];
		mi[x]=min(mi[x],min(dfs(ch[x][0]),dfs(ch[x][1])));
	}
	void kruskal(){
		for (int i=0;i<=(n<<1)+1;++i)fa[i]=i;
		sort(E+1,E+m+1);
		int fx,fy;
		cnt=n;
		for (int i=1;i<=m;++i){
			fx=find(E[i].u),fy=find(E[i].v);
			if (fx==fy)continue;
			ch[++cnt][0]=fx,ch[cnt][1]=fy;
			fa[fx]=fa[fy]=f[fx][0]=f[fy][0]=cnt;
			g[fx][0]=g[fy][0]=E[i].l;
		}
		for (int j=1;j<20;++j)
			for (int i=1;i<=(n<<1)+1;++i)
				f[i][j]=f[f[i][j-1]][j-1],
				g[i][j]=min(g[i][j-1],g[f[i][j-1]][j-1]);
		dfs(cnt);
	}
	int Find(int s,int va){
		for (int i=19;~i;--i)
			if (g[s][i]>va&&g[s][i]<inf){
				s=f[s][i];
			}
		return s;
	}
	void Query(){
		int Q,k,s,lastans=0,v,p,tot,pos;
		scanf("%d%d%d",&Q,&k,&s);
		while (Q--){
			scanf("%d%d",&v,&p);
			v=(v+k*lastans-1)%n+1;
			p=(p+k*lastans)%(s+1);
			pos=Find(v,p);
			printf("%d\n",lastans=mi[pos]);
		}
	}
	void init(){
		memset(g,0x3f,sizeof g);
		memset(f,false,sizeof f);
		memset(ch,false,sizeof ch);
		memset(mi,false,sizeof mi);
		tot=0;
	}
}

int main(){
	int T;
	scanf("%d",&T);
	while (T--){
		Deal::init();
		Graph::clear();
		scanf("%d%d",&Graph::n,&Graph::m);
		for (int i=1;i<=Graph::m;++i)
			Graph::E[i].init();
		Graph::Dijkstra(1);
		Deal::kruskal();
		Deal::Query();
	}
	return 0;
}

评测结果