代码

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 800005
#define M 1200005
using namespace std;
int fa[N],fn[N],fs[N],nt[2*M],dt[2*M],pr[2*M],sz[N],mi[N],dis[N],d[20*M],n,m,m1,rt,vl[2*N],m2,ap[N][2],am[2*M];
struct node
{
	int x,y,l,h;
}a1[M],a2[M];
bool bz[N];
bool cmp1(node x,node y)
{
	return x.h>y.h;
}
bool cmp2(node x,node y)
{
	return (x.x<y.x||(x.x==y.x&&x.h>y.h));
}
void hb(int x,int y,int z)
{
	fa[x]=y,sz[y]+=sz[x],fn[x]=z;
}
void link(int x,int y,int z)
{
	nt[++m1]=fs[x];
	dt[fs[x]=m1]=y;
	pr[m1]=z;
}
int getf(int k)
{
	if(fa[k]==0||fa[k]==k) return k;
	return getf(fa[k]);
}
void dfs(int k)
{
	mi[k]=dis[k];
	fo(i,ap[k][0],ap[k][1])
	{
		if(!i) break;
		int p=a2[i].y;
		dfs(p),mi[k]=min(mi[k],mi[p]);
		if(i==ap[k][0]) am[i]=mi[p];
		else am[i]=min(am[i-1],mi[p]);
	}
}
void spfa()
{
	memset(dis,107,sizeof(dis));
	int l=0,r=1;
	d[1]=1,dis[1]=0;
	memset(bz,0,sizeof(bz));
	bz[1]=1;
	while(l<r)
	{
		int k=d[++l];
		for(int i=fs[k];i;i=nt[i])
		{
			int p=dt[i];
			if(dis[p]>dis[k]+pr[i])
			{
				dis[p]=dis[k]+pr[i];
				if(!bz[p])
				{
					d[++r]=p;
					bz[p]=1;
					if(r!=l+1&&dis[p]<dis[d[l+1]]) swap(d[l+1],d[r]);
				}
			}
		}
		bz[k]=0;
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(fa,0,sizeof(fa));
		memset(fs,0,sizeof(fs));
		memset(ap,0,sizeof(ap));
		m1=m2=0;
		scanf("%d%d",&n,&m);
		fo(i,1,n) sz[i]=1;
		fo(i,1,m) scanf("%d%d%d%d",&a1[i].x,&a1[i].y,&a1[i].l,&a1[i].h),link(a1[i].x,a1[i].y,a1[i].l),link(a1[i].y,a1[i].x,a1[i].l);
		sort(a1+1,a1+m+1,cmp1);
		fo(i,1,m)
		{
			int fx=getf(a1[i].x),fy=getf(a1[i].y);
			if(fx!=fy)
			{
				if(sz[fx]>sz[fy]) hb(fy,fx,a1[i].h),a2[++m2].x=fx,a2[m2].y=fy,a2[m2].h=a1[i].h;
				else hb(fx,fy,a1[i].h),a2[++m2].x=fy,a2[m2].y=fx,a2[m2].h=a1[i].h;			
			}
		}
		sort(a2+1,a2+m2+1,cmp2);
		a2[0].x=-1;
		ap[a2[1].x][0]=1,ap[a2[m2].x][1]=m2;
		fo(i,2,m2) 
		{
			if(a2[i].x!=a2[i-1].x)
			{
				ap[a2[i-1].x][1]=i-1;
				ap[a2[i].x][0]=i;
			}
		}
		spfa();
		rt=getf(1);
		dfs(rt);
		int q,ans=0,lim,sc;
		scanf("%d%d%d",&q,&sc,&lim);
		fo(t1,1,q)
		{
			int st,hi;
			scanf("%d%d",&st,&hi);
			st=(st+sc*ans-1)%n+1;
			hi=(hi+sc*ans)%(lim+1);
			int k=st;
			while(fa[k]&&fn[k]>hi) k=fa[k];
			int x=ap[k][0],y=ap[k][1],s1=1802201963;
			if(x)
			{
				while(x+1<y) 
				{
					int mid=(x+y)>>1;
					if(a2[mid].h>hi) x=mid;
					else y=mid;
				}
				if(a2[y].h>hi) s1=am[y];
				else if(a2[x].h>hi) s1=am[x];
			}
			ans=min(dis[k],s1);
			printf("%d\n",ans);
		}
	}
	return 0;
}

评测结果