代码

#include<bits/stdc++.h>

using namespace std;

#define pii pair<int,int>
#define fir first
#define sec second
#define makr(x,y) make_pair(x,y)

const int N=400000+10;
const int INF=0x3f3f3f3f;

struct Edge
{
	int u,v,l,a;
}edges[N<<1];

int n,m,fir[N],nxt[N<<1],tote,d[N];

bool vis[N];

int fa[N],sz[N],upa[N],mn[N],in[N];
vector<pii> G[N];

priority_queue<pii,vector<pii>,greater<pii> > Q;

void spfa()
{
	memset(vis,0,sizeof vis);
	Q.push(makr(0,1));
	while(!Q.empty())
	{
		pii p=Q.top();Q.pop();
		if(vis[p.sec])
			continue;
		vis[p.sec]=true;
		d[p.sec]=p.fir;
		for(int i=fir[p.sec];i;i=nxt[i])
		{
			Edge& e=edges[i];
			if(!vis[e.v])
			{
				Q.push(makr(p.fir+e.l,e.v));
			}
		}
	}
}

int id[N];

bool cmp(int x,int y)
{
	return edges[x].a>edges[y].a;
}

int find(int x)
{
	return (in[x]==x)?x:(in[x]=find(in[x]));
}

void Min(int& x,int y)
{
	x=min(x,y);
}

void hb(int x,int y,int a)
{
	//cout<<x<<","<<y<<","<<a<<endl;
	x=find(x);y=find(y);
	if(x==y)
		return;
	if(sz[x]>sz[y])
		swap(x,y);
	sz[y]+=sz[x];
	Min(mn[y],mn[x]);
	upa[x]=a;
	fa[x]=y;
	in[x]=y;
}

int q,k,s;

int query(int v,int p)
{
	while(upa[v]>p)
		v=fa[v];
	int left=0,mid,right=G[v].size()-1,res=0;
	while(left<=right)
	{
		mid=(left+right)>>1;
		if(G[v][mid].fir>p)
			left=(res=mid)+1;
		else
			right=mid-1;
	}
	return G[v][res].sec;
}

void work()
{
	scanf("%d%d",&n,&m);
	memset(fir,0,sizeof fir);
	tote=0;
	for(int i=1;i<=m;++i)
	{
		++tote;
		scanf("%d%d%d%d",&edges[tote].u,&edges[tote].v,&edges[tote].l,&edges[tote].a);
		nxt[tote]=fir[edges[tote].u];fir[edges[tote].u]=tote;
		edges[tote+1]=edges[tote];++tote;
		swap(edges[tote].u,edges[tote].v);
		nxt[tote]=fir[edges[tote].u];fir[edges[tote].u]=tote;
	}
	spfa();
	for(int i=1;i<=n;++i)
		G[i].clear();
	//for(int i=1;i<=n;++i)
	//	cout<<i<<":"<<d[i]<<endl;
	for(int i=1;i<=n;++i)
	{
		fa[i]=i;
		sz[i]=1;
		upa[i]=-INF;
		mn[i]=d[i];
		in[i]=i;
	}
	for(int i=1;i<=m;++i)
		id[i]=(i<<1)-1;
	sort(id+1,id+m+1,cmp);
	for(int i=1;i<=m;++i)
		hb(edges[id[i]].u,edges[id[i]].v,edges[id[i]].a);
	for(int i=1;i<=n;++i)
	{
		if(fa[i]!=i)
			G[fa[i]].push_back(makr(upa[i],mn[i]));
		G[i].push_back(makr(INF,d[i]));
	}
	for(int i=1;i<=n;++i)
	{
		sort(G[i].rbegin(),G[i].rend());
		for(int j=1;j<(int)G[i].size();++j)
			Min(G[i][j].sec,G[i][j-1].sec);
	}
	scanf("%d%d%d",&q,&k,&s);
	int lastans=0;
	for(int i=1,v,p;i<=q;++i)
	{
		scanf("%d%d",&v,&p);
		v=(v+k*lastans-1)%n+1;
		p=(p+k*lastans)%(s+1);
		printf("%d\n",lastans=query(v,p));
	}
}

int main()
{
	//freopen("return.in","r",stdin);
	//freopen("return.out","w",stdout);
	int T;
	for(scanf("%d",&T);T--;)
		work();
	return 0;
}

评测结果