代码

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
#include <complex>
using namespace std;
inline int read(){
	int k=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
	return k*f;
}
inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
	write(x);puts("");
}
const int N=2e5+10;
using namespace std;
int rt[2*N],t[100*N],td[100*N],ls[100*N],rs[100*N],sd[100*N],n,m,cnt;
bool vis[N];int dist[N];
inline void build(int l,int r,int& nod){
	if(!nod)nod=++cnt;ls[nod]=0;rs[nod]=0;t[nod]=0;
	if(l==r){t[nod]=l;td[nod]=dist[l];return;}
	int mid=(l+r)>>1;
	build(l,mid,ls[nod]);
	build(mid+1,r,rs[nod]);
}
inline void xg(int l,int r,int& nod,int la,int p,int v){
	nod=++cnt;ls[nod]=ls[la];rs[nod]=rs[la];td[nod]=td[la];
	if(l==r){t[nod]=v;sd[nod]=sd[la];return;}
	int mid=(l+r)>>1;
	if(p<=mid)xg(l,mid,ls[nod],ls[la],p,v);
	else xg(mid+1,r,rs[nod],rs[la],p,v);
}
inline void xgd(int l,int r,int &nod,int la,int p,int v){\
	if(nod)la=nod;
	nod=++cnt;t[nod]=t[la];ls[nod]=ls[la];rs[nod]=rs[la];td[nod]=td[la];
	if(l==r){td[nod]=v;sd[nod]=sd[la];return;}
	int mid=(l+r)>>1;
	if(p<=mid)xgd(l,mid,ls[nod],ls[la],p,v);
	else xgd(mid+1,r,rs[nod],rs[la],p,v);
}
inline int s(int l,int r,int nod,int k){
	if(l==r)return nod;
	int mid=(l+r)>>1;
	if(k<=mid)return s(l,mid,ls[nod],k);
	else return s(mid+1,r,rs[nod],k);
}
inline void zj(int l,int r,int nod,int p){
	if(l==r){sd[nod]++;return;}
	int mid=(l+r)>>1;
	if(p<=mid)zj(l,mid,ls[nod],p);
	else zj(mid+1,r,rs[nod],p);
}
inline int getfather(int k,int v){
	int p=s(1,n,k,v);
	if(v==t[p])return p;
	return getfather(k,t[p]);
}
struct ppap{int x,y,v,dep;}a[2*N];
int nedge=0,p[4*N],nex[4*N],head[4*N],c[4*N];
inline void addedge(int a,int b,int v){
	p[++nedge]=b;nex[nedge]=head[a];head[a]=nedge;
	c[nedge]=v;
}
inline bool cmp(ppap a,ppap b){return a.dep==b.dep?a.v<b.v:a.dep<b.dep;}
struct qqaq{int x,v;};
bool operator <(qqaq a,qqaq b){return a.v>b.v;}
priority_queue<qqaq>q;
inline void dijkstra(){
	q.push((qqaq){1,0});
	memset(vis,0,sizeof vis);
	memset(dist,0x3f,sizeof dist);dist[1]=0;
	while(!q.empty()){
		int now=q.top().x;q.pop();
		if(vis[now])continue;vis[now]=1;
		for(int k=head[now];k;k=nex[k])
			if(!vis[p[k]]&&dist[p[k]]>dist[now]+c[k]){
			dist[p[k]]=dist[now]+c[k];
			q.push((qqaq){p[k],dist[p[k]]});
		}
	}
}
inline int check(int x){
	int l=1,r=m+1,ans=m+1;
	while(l<=r){
		int mid=l+r>>1;
		if(x<a[mid].dep)ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}
int main()
{
	for(int T=read();T;T--){
		n=read();m=read();int la=0;
		nedge=0;memset(head,0,sizeof head);
		for(int i=1;i<=m;i++){
			a[i].x=read();a[i].y=read();a[i].v=read();a[i].dep=read();
			addedge(a[i].x,a[i].y,a[i].v);
			addedge(a[i].y,a[i].x,a[i].v);
		}
		dijkstra();
		sort(a+1,a+m+1,cmp);cnt=0;
		memset(rt,0,sizeof rt);
		build(1,n,rt[m+1]);
		a[m+1].dep=1e9+7;
		for(int i=m;i;i--){
			int x=a[i].x,y=a[i].y;
			int fx=getfather(rt[i+1],x),fy=getfather(rt[i+1],y);
			if(fx==fy){rt[i]=rt[i+1];continue;}
			if(sd[fx]>sd[fy])swap(fx,fy);
			xg(1,n,rt[i],rt[i+1],t[fx],t[fy]);
			if(td[fx]<td[fy])xgd(1,n,rt[i],rt[i+1],t[fy],td[fx]);
			if(sd[fx]==sd[fy])zj(1,n,rt[i],t[fy]);
		}
		int Q=read(),K=read(),S=read(),ans=0;
		while(Q--){
			int v=(read()+K*ans-1)%n+1;
			int p=(read()+K*ans)%(S+1);
			p=check(p);
			int fx=getfather(rt[p],v);
			writeln(td[fx]);ans=td[fx];
		}
	}
	return 0;
}

评测结果