用的kru和dij最短路，题解第一篇做法但是TLE

求大佬帮

#include<bits/stdc++.h>
using namespace std;
const long long  N=2e5+10,M=4e5+10;
long long  T,n,m,u,v1,l,a,lastans=0,v0,p0,v,p;
long long  Q,K,S,head[N],tot,dist[N],flag[N]; 
struct Node{
	long long  dis,num;
	bool operator<(const Node &a)const{
		return dis>a.dis;
	}
};
priority_queue<Node>q;
struct node{
	long long  to,next,l,a;
}edge[M*2];
struct node1{
	long long  x,y,a;
	bool operator<(const node1 &x)const{
		return a>x.a;
	}
}bian[M*2];
struct node2{
	long long  son1,son2,fa;
	long long  a;//a就是海拔高度 
	long long  ans;//这个节点所有儿子的dis的最小值 
}tree[2*M];//1-n号是点节点，n+1--n+m号是边节点 
void add(long long  u,long long  v,long long  l,long long  a){
	tot++;
	edge[tot].to=v;
	edge[tot].next=head[u];
	edge[tot].l=l;
	edge[tot].a=a;
	head[u]=tot;
}
void dij(long long  x){
	dist[x]=0;
	q.push((Node){0,1});
	while(!q.empty()){
		Node now;
		now=q.top();
		q.pop();
		flag[now.num]=1;
		for(long long  i=head[now.num];i;i=edge[i].next){
			if(flag[edge[i].to]) continue;
			if(now.dis+edge[i].l<dist[edge[i].to]){
				dist[edge[i].to]=now.dis+edge[i].l;
				q.push((Node){dist[edge[i].to],edge[i].to});
			}
		}
	}
	return ;
}
long long  find_fa(long long  x){
	if(tree[x].fa==x) return x;
	else return find_fa(tree[x].fa);
}
long long  find_fa_s(long long  x,long long  p){
	if(tree[x].fa==x||tree[tree[x].fa].a<=p) return tree[x].ans;
	else return find_fa_s(tree[x].fa,p);
}
void kru(){
	sort(bian+1,bian+1+m);
	for(long long  i=1;i<=n;i++) tree[i].ans=dist[i];
	for(long long  i=1;i<=m;i++){
		long long  fa_x=find_fa(bian[i].x);
		long long  fa_y=find_fa(bian[i].y);
		if(fa_x==fa_y){
			continue;
		}
		tree[fa_x].fa=n+i;
		tree[fa_y].fa=n+i; 
		tree[n+i].son1=fa_x;
		tree[n+i].son2=fa_y;
		tree[n+i].a=bian[i].a;
		tree[n+i].ans=min(tree[fa_x].ans,tree[fa_y].ans);
	}
}
void qk(){
	for(long long  i=1;i<=M*2;i++)edge[i].to=edge[i].next=edge[i].l=edge[i].a=0;
	for(long long  i=1;i<=M;i++) bian[i].x=bian[i].y=bian[i].a=0;
	for(long long  i=1;i<=M*2;i++){
		tree[i].son1=tree[i].son2=0;
		tree[i].ans=tree[i].a=0x3f3f3f3f;
		tree[i].fa=i;
	}
	memset(head,0,sizeof(head));
	memset(dist,127,sizeof(dist));
	memset(flag,0,sizeof(flag));
	q=priority_queue<Node>();
	n=m=lastans=tot=v=v0=p=p0=0;
}
int main(){
	//freopen("1.txt","r",stdin);
	//freopen("2.txt","w",stdout);
	scanf("%lld",&T);
	while(T--){
		qk();
		scanf("%lld%lld",&n,&m);
		for(long long  i=1;i<=m;i++){
			scanf("%lld%lld%lld%lld",&u,&v1,&l,&a);
			add(u,v1,l,a);
			add(v1,u,l,a);
			bian[i].x=u;bian[i].y=v1;bian[i].a=a;
		}
		dij(1);
		kru();
		scanf("%lld%lld%lld",&Q,&K,&S);
		for(long long  i=1;i<=Q;i++){
			scanf("%lld%lld",&v0,&p0);
			v=(v0+K*lastans-1)%n+1;
			p=(p0+K*lastans)%(S+1);
			lastans=find_fa_s(v,p);
			printf("%lld\n",lastans);
		}
	}
	return 0;
}