RT，30pts，做法 可持久化并查集+Dijkstra （（（

先对边的高度排序，再一个一个加入，用可持久化线段树维护每个联通块的最短路径的最值

然后满屏 WA+TLE，求助/kel

#include<algorithm>
#include<cstdio>
#include<queue>
#define DEBUG printf("Baylor AK IOI!!!\n");
const int M=2e5+5,INF=0x7fffffff;
int T,n,m,q,k,s,tot,tim,d[M],root[M],lsh[M<<1];bool vis[M];
inline int min(const int&a,const int&b){
	return a>b?b:a;
}
inline int Add(const int&a,const int&b,const int&mod){
	return a+b>=mod?a+b-mod:a+b;
}
/*-----------------------------------------SSSP---------------------------------------*/
struct Edge{
	int to,val;Edge*nx;
}e[M<<2],*h[M],*cnt;
struct Heap{
	int id,dis;
	Heap(int id=0,int dis=0):id(id),dis(dis){}
	inline bool operator<(const Heap&it)const{
		return dis<it.dis;
	}
};
inline void Dijkstra(const int&s){
	register int i,u,v;register Edge*E;
	std::priority_queue<Heap>q;
	for(i=1;i<=n;++i)d[i]=INF,vis[i]=false;
	q.push(Heap(1,d[s]=0));
	while(!q.empty()){
		u=q.top().id;q.pop();
		if(vis[u])continue;
		for(E=h[u];E;E=E->nx){
			v=E->to;
			if(!vis[v]&&d[u]+E->val<d[v]){
				q.push(Heap(v,d[v]=d[u]+E->val));
			}
		}
	}
}
/*-------------------------------------SegmentTree-------------------------------------*/
struct Node{
	int L,R,f,siz,min;
}t[M<<7];
inline int nnd(){
	t[++tot]=(Node){0,0,0,0};
	return tot;
}
void build(int&u,int L,int R){
	u=nnd();
	if(L<R){
		int mid=L+R>>1;
		build(t[u].L,L,mid);build(t[u].R,mid+1,R);
	}
	else t[u].f=L,t[u].siz=1,t[u].min=d[L];
}
/*------------------------------DSU in SegmentTree Modify------------------------------*/
int Modify1(int u,int x,int val,int L=1,int R=n){
	int id=nnd();
	t[id]=t[u];
	if(L<R){
		int mid=L+R>>1;
		if(x<=mid)t[id].L=Modify1(t[u].L,x,val,L,mid);
		else t[id].R=Modify1(t[u].R,x,val,mid+1,R);
	}
	else t[id].f=val;
	return id;
}
int Modify2(int u,int x,int v1,int v2,int L=1,int R=n){
	int id=nnd();
	t[id]=t[u];
	if(L<R){
		int mid=L+R>>1;
		if(x<=mid)t[id].L=Modify2(t[u].L,x,v1,v2,L,mid);
		else t[id].R=Modify2(t[u].R,x,v1,v2,mid+1,R);
	}
	else t[id].siz=v1,t[id].min=v2;
	return id;
}
/*-------------------------------DSU in SegmentTree Query------------------------------*/
int&Findf(int&u,int x,int L=1,int R=n){
	if(L==R)return t[u].f;
	int mid=L+R>>1;
	if(x<=mid)return Findf(t[u].L,x,L,mid);
	else return Findf(t[u].R,x,mid+1,R);
}
int&Finds(int&u,int x,int L=1,int R=n){
	if(L==R)return t[u].siz;
	int mid=L+R>>1;
	if(x<=mid)return Finds(t[u].L,x,L,mid);
	else return Finds(t[u].R,x,mid+1,R);
}
int&Findm(int&u,int x,int L=1,int R=n){
	if(L==R)return t[u].min;
	int mid=L+R>>1;
	if(x<=mid)return Findm(t[u].L,x,L,mid);
	else return Findm(t[u].R,x,mid+1,R);
}
/*-----------------------------------------DSU-----------------------------------------*/
int Find(const int&u,const int&t=tim){
	int&f=Findf(root[t],u);
	return f==u?u:f=Find(f);
}
inline void Merge(const int&u,const int&v){
	int&su=Finds(root[tim],u),&sv=Finds(root[tim],v);
	int mi=min(Findm(root[tim],u),Findm(root[tim],v));
	if(su>sv)root[tim+1]=Modify2(Modify1(root[tim],v,u),u,su+sv,mi);
	else root[tim+1]=Modify2(Modify1(root[tim],u,v),v,su+sv,mi);
	++tim;
}
/*-----------------------------------------Main----------------------------------------*/
struct edge{
	int u,v,val,high;
	edge(int u=0,int v=0,int val=0,int high=0):u(u),v(v),val(val),high(high){}
	inline bool operator<(const edge&it)const{
		return high>it.high;
	}
	inline void add()const{
		*cnt=(Edge){v,val,h[u]};h[u]=cnt++;
		*cnt=(Edge){u,val,h[v]};h[v]=cnt++;
	}
}E[M<<1];
signed main(){
	register int i,u,v,p,x;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);cnt=e;tot=tim=x=0;
		for(i=1;i<=n;++i)h[i]=NULL;
		for(i=1;i<=m;++i){
			scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].val,&E[i].high);
			root[i]=0;E[i].add();lsh[i]=E[i].high;
		}
		std::sort(lsh+1,lsh+m+1);
		std::sort(E+1,E+n+1);Dijkstra(1);build(root[0],1,n);
		for(i=1;i<=m;++i){
			u=Find(E[i].u);v=Find(E[i].v);
			if(u!=v)Merge(u,v);
		}
		scanf("%d%d%d",&q,&k,&s);++s;
		for(i=1;i<=q;++i){
			scanf("%d%d",&v,&p);
			v=Add(v,k*x-1,n)+1;p=Add(p,k*x,s);
			p=p<lsh[1]?1:std::lower_bound(lsh+1,lsh+m+1,p+1)-lsh;
			printf("%d\n",x=Findm(root[m-p+1],Find(v,m-p+1)));
		}
	}
}