代码

#include<bits/stdc++.h>
#define ll long long 
#define mp make_pair
using namespace std;
typedef pair<int,int> pa;
inline int read(){int w=1,s=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-') w=-1;ch=getchar();}while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();} return w*s;}
int fa[3000010],cnt,rt,h[3000010],tot,tot1,h2[3000010],size[3000100],val[3000001];
ll dis[3000100];
struct node{
	int u,v,w,H;
}e[1000010];
struct edge 
{
	int to,next,w;
}E[1000100],E1[1000010];
int n,m,ANS;
int find(int k){if(fa[k]==k) return k;else return fa[k]=find(fa[k]);}
int anc[1000010][20];
int vis[1000100];
int query(int x,int y) {
	for(register int i=19;i>=0;--i) if(val[anc[x][i]]>y) x=anc[x][i];
	return dis[x];
}
inline void add1(int from,int to,int w){
	E[++tot].to=to;E[tot].next=h[from];E[tot].w=w;h[from]=tot;
}
inline void add2(int from,int  to){
	E1[++tot1].to=to;E1[tot1].next=h2[from];h2[from]=tot1;
}
inline bool cmp(node p,node q){return p.H>q.H;}
void DFS(int now,int ffa)
{
	vis[now]=1;
	for(register int i=h2[now];i;i=E1[i].next)
	{	int to=E1[i].to;if(to==ffa) continue;if(vis[to]) continue;DFS(to,now);
		dis[now]=min(dis[now],dis[to]);
	}
}
inline void dij(int s)
{
	priority_queue<pa, vector<pa>, greater<pa> > que; 
	que.push(mp(0,s));memset(dis,0x3f,sizeof(dis));dis[s]=0;
	while(!que.empty())
	{
		pa tmp=que.top();que.pop();
		int u=tmp.second;if(dis[u]!=tmp.first) continue;
		for(register int i=h[u];i;i=E[i].next)
		{	int to=E[i].to;
			if(dis[to]>dis[u]+E[i].w){
				dis[to]=dis[u]+E[i].w;que.push(mp(dis[to],to));
			}
		}
	}
}
inline void build_st(){for(register int i=1;i<=19;++i) for(register int j=1;j<=cnt;++j) anc[j][i]=anc[anc[j][i-1]][i-1];}
inline void solve(){
	val[0]=-1e9;
	for(register int i=1,u,v,w,H;i<=m;++i) u=read(),v=read(),w=read(),H=read(),e[i].u=u,e[i].v=v,e[i].w=w,e[i].H=H,add1(u,v,w),add1(v,u,w);
	for(register int i=1;i<=n;++i) fa[i]=i,size[i]=1;
	sort(e+1,e+m+1,cmp);cnt=n;
	for(register int i=1;i<=m;++i)
	{
		int u=e[i].u,v=e[i].v;u=find(u);v=find(v);
		if(u!=v)
		{
			++cnt;
			fa[u]=cnt;fa[v]=cnt;val[cnt]=e[i].H;add2(u,cnt);add2(v,cnt);add2(cnt,v);add2(cnt,u);
			anc[u][0]=cnt,anc[v][0]=cnt;fa[cnt]=cnt;
		}
	}dij(1);DFS(find(1),0);build_st();int q=read(),k=read(),s=read();
//	for(register int i=0;i<=2;++i) for(register int j=1;j<=cnt;++j) cout<<i<<" "<<j<<" "<<anc[j][i]<<"\n"; 
	for(register int i=1;i<=q;++i)
	{
		ll u=read(),H=read();u=(u+1ll*k*ANS-1)%n+1;H=(H+1ll*k*ANS)%(s+1);
		cout<<(ANS=query(u,H))<<"\n";
	}
}
int main(){
//	freopen("return5.in","r",stdin);
//	freopen("return5.out","w",stdout);
	int t=read();
	while(t--)
	{
		tot=0;memset(h,0,sizeof(h));tot1=0;memset(h2,0,sizeof(h2));memset(vis,0,sizeof(vis));
		n=read(),m=read();
		solve();
	}
	return 0;
}

评测结果