代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define ll long long
#define MAX 200200
#define pir pair<int,int> 
#define mpi make_pair
#define fr(x) (x.first)
#define sd(x) (x.second)
#define lson (now<<1)
#define rson (now<<1|1)
inline int read()
{
	int x=0;bool fl=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')fl=true,ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
	return fl?-x:x;
}
struct Edge{int u,v,w,s;}E[MAX<<1];
bool operator<(Edge a,Edge b){return a.s>b.s;}
struct Line{int v,next,w,s;}e[MAX<<2];
int h[MAX<<1],cnt=1;
inline void Add(int u,int v,int w,int s){e[cnt]=(Line){v,h[u],w,s};h[u]=cnt++;}
int n,m,dis[MAX],Q,typ,S;
bool vis[MAX];
namespace SP
{
	priority_queue<pir,vector<pir>,greater<pir> >Q;
	void Dijkstra()
	{
		memset(vis,0,sizeof(vis));
		while(!Q.empty())Q.pop();
		Q.push(mpi(0,1));
		while(!Q.empty())
		{
			pir u=Q.top();Q.pop();
			if(vis[sd(u)])continue;vis[sd(u)]=true;
			dis[sd(u)]=fr(u);
			for(int i=h[sd(u)];i;i=e[i].next)
				if(!vis[e[i].v])Q.push(mpi(dis[sd(u)]+e[i].w,e[i].v));
		}
	}
}
namespace MST
{
	int f[MAX<<1],id;
	int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}
	void init(){for(int i=1;i<=n<<1;++i)f[i]=i;id=n;}
	void Kursual()
	{
		init();
		for(int i=1;i<=m;++i)
		{
			int u=getf(E[i].u),v=getf(E[i].v);
			if(u==v)continue;++id;
			Add(id,u,E[i].w,E[i].s);Add(id,v,E[i].w,E[i].s);
			f[u]=f[v]=id;
		}
	}
}
int dfn[MAX<<1],low[MAX<<1],tim,ln[MAX<<1];
int p[20][MAX<<1],s[20][MAX<<1];
void dfs(int u)
{
	if(u<=n)dfn[u]=++tim,ln[tim]=u;else dfn[u]=1e9;
	for(int i=1;i<20;++i)p[i][u]=p[i-1][p[i-1][u]];
	for(int i=1;i<20;++i)s[i][u]=min(s[i-1][u],s[i-1][p[i-1][u]]);
	for(int i=h[u];i;i=e[i].next)
	{
		p[0][e[i].v]=u;s[0][e[i].v]=e[i].s;
		dfs(e[i].v);dfn[u]=min(dfn[u],dfn[e[i].v]);
	}
	low[u]=tim;
}
void init(){memset(h,0,sizeof(h));cnt=1;tim=0;}
int t[MAX<<2];
void Build(int now,int l,int r)
{
	if(l==r){t[now]=dis[ln[l]];return;}
	int mid=(l+r)>>1;
	Build(lson,l,mid);Build(rson,mid+1,r);
	t[now]=min(t[lson],t[rson]);
}
int Query(int now,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)return t[now];
	int mid=(l+r)>>1,ret=2147483647;
	if(L<=mid)ret=min(ret,Query(lson,l,mid,L,R));
	if(R>mid)ret=min(ret,Query(rson,mid+1,r,L,R));
	return ret;
}
int Jump(int u,int r)
{
	for(int i=19;~i;--i)
		if(p[i][u]&&s[i][u]>r)u=p[i][u];
	return u;
}
int main()
{
	freopen("return.in","r",stdin);
	freopen("return.out","w",stdout);
	int T=read();
	while(T--)
	{
		init();n=read();m=read();
		for(int i=1;i<=m;++i)
		{
			int u=read(),v=read(),l=read(),s=read();
			E[i]=(Edge){u,v,l,s};
			Add(E[i].u,E[i].v,E[i].w,E[i].s);
			Add(E[i].v,E[i].u,E[i].w,E[i].s);
		}
		sort(&E[1],&E[m+1]);
		SP::Dijkstra();init();
		memset(p,0,sizeof(p));memset(s,0,sizeof(s));
		MST::Kursual();dfs(MST::id);
		Build(1,1,n);
		Q=read();typ=read();S=read();
		int lans=0,v,p;
		while(Q--)
		{
			v=(read()+typ*lans-1)%n+1;
			p=(read()+typ*lans)%(S+1);
			v=Jump(v,p);
			printf("%d\n",lans=Query(1,1,n,dfn[v],low[v]));
		}
	}
	return 0;
}

评测结果