代码

#include<cstdio>
#include<cstring>
#include<queue>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
using namespace std;
const int inf=1999999999;
int n,m,doe,Q,K,lastans;
int pre[808080],now[202020],son[808080],v[808080];
int fa[202020],fa_t[202020],deep[202020];
bool br[202020];
ll f[202020];

struct node
{
	int t,s;
};
vector<node>s[202020];
struct Node
{
	int x,y,w;
}line[404040];

inline void read(int &x)
{
    int data=0,W=1;
    char ch=0;
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') W=-1,ch=getchar();
    while (ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^'0'),ch=getchar();
    x=data*W;
}
bool cmp(Node uu,Node ww){return uu.w>ww.w;}
void add_line(int x,int y,int z)
{
	++doe;
	pre[doe]=now[x];
	now[x]=doe;
	son[doe]=y;
	v[doe]=z;
}

typedef pair<ll,int> pi;
void SPFA()
{
	priority_queue<pi,vector<pi>,greater<pi> >q;
	memset(f,0x3f,sizeof(f));
	memset(br,0,sizeof(br));
	f[1]=0,q.push(pi(0,1));
	int u;
	pi x;
	while(!q.empty())
	{
		x=q.top(),q.pop();
		u=x.second;
		if(!br[u])
		{
			br[u]=1;
			int p=now[u];
			while (p)
			{
				int y=son[p];
				if(f[y]>=x.first+v[p])
				{
					f[y]=x.first+v[p];
					q.push(pi(f[y],y));
				}
				p=pre[p];
			}	
		}
	}
}
void add(int x,int sss,int t)
{
	int len=s[x].size()-1;
	node kkk=(node){t,sss};
	if (kkk.s<s[x][len].s)
		s[x].push_back(kkk);
}

void merge(int x,int y,int t)
{
	while (fa[x]) x=fa[x];
	while (fa[y]) y=fa[y];
	if (x==y) return;
	if (deep[x]>deep[y]) swap(x,y);
	fa[x]=y;
	fa_t[x]=t;
	deep[y]=max(deep[y],deep[x]+1);
	add(y , s[x][s[x].size()-1].s , t);
}
void sol(int x,int t)
{
	while (fa[x] && fa_t[x]>t) x=fa[x];

	int ans=2100000000;
	int l=0,r=s[x].size()-1;
	while (l<=r)
	{
		int mid=(l+r)/2;
		if (s[x][mid].t>t) ans=min(ans,s[x][mid].s),l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",ans);
	lastans=ans;
}
int main()
{
	int T;
	scanf("%d",&T);
	while (T--)
	{
		doe=0; lastans=0;
		memset(pre,0,sizeof(pre));
		memset(now,0,sizeof(now));
		scanf("%d%d",&n,&m);
		int x,y,z1,z2;
		for (int i=1;i<=m;++i)
		{
			read(x); read(y); read(z1); read(z2);
			add_line(x,y,z1);
			add_line(y,x,z1);
			line[i].x=x; line[i].y=y; line[i].w=z2;
		}
		SPFA();

		memset(deep,0,sizeof(deep));
		memset(fa,0,sizeof(fa));
		for (int i=1;i<=n;++i)
		{
			s[i].clear();
			node kkk=(node){inf,(int)f[i]};
			s[i].push_back(kkk);
		}
		sort(line+1,line+1+m,cmp);
		for (int i=1;i<=m;++i) merge(line[i].x,line[i].y,line[i].w);
		
		scanf("%d%d%d",&Q,&K,&doe);
		for (int i=1;i<=Q;++i)
		{
			read(x); read(y);
			x=((ll)x+(ll)K*lastans-1)%n+1;
			y=((ll)y+(ll)K*lastans)%(doe+1);
			sol(x,y);
		}
	}
	return 0;
}

评测结果