代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;

const int N=200050,M=800050,INF=0x7f7f7f7f;
int n,m,Q,to[M],ne[M],head[N],cnt,L[M],H[M];

int read(){
	int x=0;char ch=getchar();
	while(ch<'0' || ch>'9')ch=getchar();
	while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();
	return x;
}
void add(int u,int v,int l,int h){
	to[++cnt]=v;ne[cnt]=head[u];head[u]=cnt;
	L[cnt]=l;H[cnt]=h;
}

struct node{
	int x,dist;
};
bool operator <(node x,node y){return x.dist<y.dist;}
priority_queue<node> pq;
int dis[N],vis[N];
void dijkstra(){
	memset(dis,0x7f,sizeof(dis));dis[1]=0;
	memset(vis,0,sizeof(vis));
	while(!pq.empty())pq.pop();
	pq.push((node){1,0});
	for(int i=1;i<=n;i++){
		while(!pq.empty() && vis[pq.top().x])pq.pop();
		int x=pq.top().x,dist=-pq.top().dist;pq.pop();
		vis[x]=1;
		for(int j=head[x];j;j=ne[j])if(!vis[to[j]] && dis[x]+L[j]<dis[to[j]]){
			dis[to[j]]=dis[x]+L[j];
			pq.push((node){to[j],-dis[to[j]]});
		}
	}
}

struct Edge{
	int u,v,h;
}E[M];
bool cmp(Edge x,Edge y){return x.h>y.h;}

int fa[N<<2],mindis[N<<2],minH[N<<2],tot,ch[N<<2][2],F[N<<2][21],dep[N<<2],lg;
int findf(int x){
	if(fa[x]==x)return x;
	return fa[x]=findf(fa[x]);
}
void DFS(int x){
	if(x<=n)return;
	dep[ch[x][0]]=dep[ch[x][1]]=dep[x]+1;
	DFS(ch[x][0]);DFS(ch[x][1]);
}
void init(){
	for(lg=1;(1<<lg)<=tot;lg++);
	for(int i=1;i<=lg;i++){
		for(int j=1;j<=tot;j++){
			F[j][i]=F[F[j][i-1]][i-1];
		}
	}
}
void kruskal(){
	for(int i=1;i<=n;i++)fa[i]=i,dep[i]=1,mindis[i]=dis[i];
	tot=n;
	for(int i=1;i<=m;i++){
		int fx=findf(E[i].u),fy=findf(E[i].v);
		if(fx!=fy){
			fa[fx]=fa[fy]=++tot;fa[tot]=tot;
			ch[tot][0]=fx;ch[tot][1]=fy;
			F[fx][0]=F[fy][0]=tot;
			mindis[tot]=min(mindis[fx],mindis[fy]);
			minH[tot]=E[i].h;
		}
	}
	dep[tot]=1;
	DFS(tot);init();
}
int LCA(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	int d=dep[x]-dep[y];
	for(int i=lg;~i;i--)if((1<<i)&d)x=F[x][i];
	if(x==y)return x;
	for(int i=lg;~i;i--)if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];
	return F[x][0];
}
int Solve(int v,int p){
	int lca=LCA(v,1);
	for(int i=lg;~i;i--)if(dep[F[v][i]]>=dep[lca] && p<minH[F[v][i]])v=F[v][i];
	return mindis[v];
}
void mian(){
	n=read();m=read();
	memset(head,0,sizeof(head));
	memset(ne,0,sizeof(ne));
	cnt=0;
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),l=read(),h=read();
		add(u,v,l,h);add(v,u,l,h);
		E[i]=(Edge){u,v,h};
	}
	dijkstra();
	sort(E+1,E+m+1,cmp);
	kruskal();
	Q=read();
	int K=read(),S=read(),lastans=0;
	while(Q--){
		int v=read(),p=read();
		if(K==1)v=(v+lastans-1)%n+1,p=(p+lastans)%(S+1);
		printf("%d\n",lastans=Solve(v,p));
	}
}

int main(){
	int T;scanf("%d",&T);
	while(T--)mian();
	return 0;
}

评测结果