代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
namespace Seg
{
int d[32000000],lc[32000000],rc[32000000],mem;
int getnode(int fr)
{
	int t=++mem;lc[t]=lc[fr];rc[t]=rc[fr];d[t]=d[fr];
	return t;
}
void setx_1(int L,int x,int l,int r,int &num)
{
	if(!num)	num=getnode(0);
	if(l==r)	{d[num]=x;return;}
	int mid=l+((r-l)>>1);
	if(L<=mid)	setx_1(L,x,l,mid,lc[num]);
	else	setx_1(L,x,mid+1,r,rc[num]);
}
void setx(int L,int x,int l,int r,int &num)
{
	num=getnode(num);
	if(l==r)	{d[num]=x;return;}
	int mid=l+((r-l)>>1);
	if(L<=mid)	setx(L,x,l,mid,lc[num]);
	else	setx(L,x,mid+1,r,rc[num]);
}
int getx(int L,int l,int r,int num)
{
	if(l==r)	return d[num];
	int mid=l+((r-l)>>1);
	if(L<=mid)	return getx(L,l,mid,lc[num]);
	else	return getx(L,mid+1,r,rc[num]);
}
}
struct E
{
	int to,nxt,l,a;
}e[800100];
int f1[200100],ne,nee;
int n,m,Q,K,S;
struct EE
{
	int x,y,a;
}ee[400100];
bool operator<(const EE &a,const EE &b)	{return a.a>b.a;}
bool operator<(const EE &a,int b)	{return a.a>b;}
int rfa[400100],rmm[400100],rd[400100];
ll d[200100];
namespace D
{
priority_queue<pli,vector<pli>,greater<pli> > pq;
bool vis[200100];
void dij()
{
	pli t;
	int u,k;
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	d[1]=0;pq.push(mp(0,1));
	while(!pq.empty())
	{
		t=pq.top();pq.pop();
		u=t.se;
		if(vis[u])	continue;
		vis[u]=1;
		for(k=f1[u];k;k=e[k].nxt)
			if(d[e[k].to]>d[u]+e[k].l)
			{
				d[e[k].to]=d[u]+e[k].l;
				pq.push(mp(d[e[k].to],e[k].to));
			}
	}
}
}
namespace S1
{
struct QQ
{
	int v,p,num;
}q[400100];
bool operator<(const QQ &a,const QQ &b)	{return a.p>b.p;}
int ans[400100];
int fa[200100],mm[200100];
int find(int x)	{return x==fa[x]?x:fa[x]=find(fa[x]);}
void unionn(int x,int y)
{
	x=find(x);y=find(y);
	if(x==y)	return;
	fa[x]=y;mm[y]=min(mm[x],mm[y]);
}
void sol()
{
	int i,j;
	for(i=1;i<=Q;i++)
	{
		scanf("%d%d",&q[i].v,&q[i].p);q[i].num=i;
		//q[i].v=(q[i].v-1)%n+1;
		//q[i].p%=(S+1);
	}
	sort(q+1,q+Q+1);sort(ee+1,ee+nee+1);
	for(i=1;i<=n;i++)	fa[i]=i,mm[i]=d[i];
	for(i=1,j=0;i<=Q;i++)
	{
		while(ee[j+1].a>q[i].p)	j++,unionn(ee[j].x,ee[j].y);
		ans[q[i].num]=mm[find(q[i].v)];
	}
	for(i=1;i<=Q;i++)	printf("%d\n",ans[i]);
}
}
int find(int x,int r)
{
	int t;
	while(1)
	{
		t=Seg::getx(x,1,n,rfa[r]);
		if(t==x)	return x;
		x=t;
	}
}
void unionn(int x,int y,int r)
{
	x=find(x,r);y=find(y,r);
	if(x==y)	return;
	int dx=Seg::getx(x,1,n,rd[r]),dy=Seg::getx(y,1,n,rd[r]);
	int mx=Seg::getx(x,1,n,rmm[r]),my=Seg::getx(y,1,n,rmm[r]);
	if(dx<dy)
	{
		Seg::setx(x,y,1,n,rfa[r]);
		Seg::setx(y,min(mx,my),1,n,rmm[r]);
	}
	else
	{
		Seg::setx(y,x,1,n,rfa[r]);
		Seg::setx(x,min(mx,my),1,n,rmm[r]);
		if(dx==dy)	Seg::setx(x,dx+1,1,n,rd[r]);
	}
}
int main()
{
	freopen("return.in","r",stdin);
	freopen("return.out","w",stdout);
	int T,a,b,c,dd,i,lans,v,p;
	scanf("%d",&T);
	while(T--)
	{
		memset(f1,0,sizeof(f1));ne=nee=0;Seg::mem=0;lans=0;
		memset(rfa,0,sizeof(rfa));
		memset(rmm,0,sizeof(rmm));
		memset(rd,0,sizeof(rd));
		scanf("%d%d",&n,&m);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d%d",&a,&b,&c,&dd);
			e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;e[ne].l=c;e[ne].a=dd;
			e[++ne].to=a;e[ne].nxt=f1[b];f1[b]=ne;e[ne].l=c;e[ne].a=dd;
			ee[++nee].x=a;ee[nee].y=b;ee[nee].a=dd;
		}
		scanf("%d%d%d",&Q,&K,&S);
		D::dij();
		if(K==0)	{S1::sol();continue;}
		sort(ee+1,ee+nee+1);
		for(i=1;i<=n;i++)
		{
			Seg::setx_1(i,i,1,n,rfa[0]);
			Seg::setx_1(i,d[i],1,n,rmm[0]);
		}
		for(i=1;i<=nee;i++)
		{
			rfa[i]=rfa[i-1];rmm[i]=rmm[i-1];rd[i]=rd[i-1];
			unionn(ee[i].x,ee[i].y,i);
		}
		for(i=1;i<=Q;i++)
		{
			scanf("%d%d",&v,&p);
			if(K)	v=(v+lans-1)%n+1,p=(p+lans)%(S+1);
			p=lower_bound(ee+1,ee+nee+1,p)-ee-1;
			lans=find(v,p);lans=Seg::getx(lans,1,n,rmm[p]);
			printf("%d\n",lans);
		}
	}
	return 0;
}

评测结果