代码

#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<queue>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#define sqr(x) (x)*(x)
#define fz1(i,n) for (i=1;i<=n;i++)
#define fd1(i,n) for (i=n;i>=1;i--)
#define fz0g(i,n) for (i=0;i<=n;i++)
#define fd0g(i,n) for (i=n;i>=0;i--)
#define fz0k(i,n) for (i=0;i<n;i++)
#define fd0k(i,n) for (i=(long long)(n-1);i>=0;i--)
#define fz(i,x,y) for (i=x;i<=y;i++)
#define fd(i,y,x) for (i=y;i>=x;i--)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len) {char ss[len];scanf("%s",ss);(st)=ss;}
using namespace std;
int n,m,q,k,s,i,j,dis[200005],fa[600005][20],mi[600005],t,par[600005],cnt,l[600005],r[600005],val[600005],x,y,vis[200005];
vector<int> all;
struct bian
{
	int x,y,l,a;
}bi[400005];
vector<int> bi2[200005];
int fnd(int x)
{
	if (par[x]==x) return x;
	return par[x]=fnd(par[x]);
}
void dijkstra()
{
	priority_queue<pair<int,int> > pq;
	memset(dis,-1,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[1]=0;
	pq.push(make_pair(0,1));
	int i;
	while (!pq.empty())
	{
		int x=pq.top().second;
		pq.pop();
if (vis[x]) continue;
vis[x]=1;
		for (i=0;i<bi2[x].size();i++)
		{
			int y=bi[bi2[x][i]].x^bi[bi2[x][i]].y^x;
			int z=dis[x]+bi[bi2[x][i]].l;
			if (dis[y]==-1||dis[y]>z)
			{
				dis[y]=z;
				pq.push(make_pair(-z,y));
			}
		}
	}
}
bool cmp(bian x,bian y)
{
	return x.a>y.a;
}
void mst()
{
	int i;
	memset(l,0,sizeof(l));
	memset(r,0,sizeof(r));
	memset(val,0,sizeof(val));
	fz1(i,n) par[i]=i;
	fz1(i,n) mi[i]=dis[i];
	stable_sort(bi+1,bi+m+1,cmp);
	cnt=n;
	fz1(i,m)
	{
		if (fnd(bi[i].x)!=fnd(bi[i].y))
		{
			cnt++;
			l[cnt]=fnd(bi[i].x);
			r[cnt]=fnd(bi[i].y);
			fa[fnd(bi[i].x)][0]=cnt;
			fa[fnd(bi[i].y)][0]=cnt;
			mi[cnt]=min(mi[fnd(bi[i].x)],mi[fnd(bi[i].y)]);
			val[cnt]=bi[i].a;
			par[cnt]=par[fnd(bi[i].x)]=par[fnd(bi[i].y)]=cnt;
		}
	}
	fz1(j,19)
	{
		fz1(i,cnt)
		{
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
}
int query(int x,int y)
{
	int i;
	for (i=19;i>=0;i--)
	{
		if (val[fa[x][i]]>y)
		{
			x=fa[x][i];
		}
	}
	return mi[x];
}
int main()
{
//	freopen("return.in","r",stdin);
//	freopen("return.out","w",stdout);
	scanf("%d",&t);
	while (t--)
	{
		//cerr<<t<<endl;
		all.clear();
		scanf("%d%d",&n,&m);
		fz1(i,n) bi2[i].clear();
		fz1(i,m)
		{
			scanf("%d%d%d%d",&bi[i].x,&bi[i].y,&bi[i].l,&bi[i].a);
			bi2[bi[i].x].push_back(i);
			bi2[bi[i].y].push_back(i);
		}
		dijkstra();
		mst();
		scanf("%d%d%d",&q,&k,&s);
		int ans=0;
		while (q--)
		{
			scanf("%d%d",&x,&y);
			x=(x+k*ans-1)%n+1;
			y=(y+k*ans)%(s+1);
			printf("%d\n",ans=query(x,y));
		}
	}
	return 0;
}

评测结果