代码

#include<cstdio>
#include<cstring>
#include<queue>
#include<ext/pb_ds/assoc_container.hpp>
#define neko 1000010
#define meko 1000010
#define qeko 1000010
#define fi first
#define se second
#define chkmin(a,b) ((a)<(b)?(a):(b))
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
using namespace std;
typedef long long ll;
typedef pair<ll,int> pi;
struct qwq
{ll ver,ans;};
vector<qwq>vec[neko];
struct node
{int u,v,h,nex;ll w;}e[meko<<1],E[meko];
int t,Et,tp,n,m,Q,K,maxA;
typedef int arr[neko];
arr head,fa,verfa,book,dep;
ll mindis[neko],dis[neko],ans[neko],inf=2e9+1e8,lastans;
template<typename T>
void read(T &x)
{
	char c=getchar();x=0;
	while(!isdigit(c))c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
}
namespace Path
{
	void add(int x,int y,ll z,int o)
	{
		e[++t].u=E[++Et].u=x;
		e[t].v=E[Et].v=y;
		e[t].w=E[Et].w=z;
		e[t].h=E[Et].h=o;
		e[t].nex=head[x];
		head[x]=t;
		e[++t].u=y;
		e[t].v=x;
		e[t].w=z;
		e[t].h=o;
		e[t].nex=head[y];
		head[y]=t;
	}
	void dijkstra()
	{
		priority_queue<pi,vector<pi>,greater<pi> >q;
		memset(dis,0x3f,sizeof(dis));
		dis[1]=0,q.push(pi(0,1));
		int u;pi x;
		while(!q.empty())
		{
			x=q.top(),q.pop();
			u=x.se;
			if(!book[u])
			{
				book[u]=1;
				for(register int i=head[u],v=e[i].v;i;i=e[i].nex,v=e[i].v)
				{
					if(dis[v]>=x.fi+e[i].w)
					{
						dis[v]=x.fi+e[i].w;
						q.push(pi(dis[v],v));
					}
				}
			}
		}
	}
}
namespace Uset
{
	int find(int x)
	{
		while(fa[x])x=fa[x];
		return x;
	}
	void insert(int x,ll nowans,ll ver)
	{
		int len=vec[x].size()-1;
		if(nowans<vec[x][len].ans)vec[x].push_back((qwq){ver,nowans});
		//printf("xx %lld %lld\n",ver,nowans);
	}
	void merge(int u,int v,ll w)
	{
		int x=find(u),y=find(v);	
		if(x^y)
		{
			if(dep[x]>dep[y])std::swap(x,y);
			fa[x]=y,verfa[x]=w;
			dep[y]=chkmax(dep[x]+1,dep[y]);
			insert(y,vec[x][vec[x].size()-1].ans,w);
		}
	}
	ll solve(int x,int ver)
	{
		while(fa[x]&&verfa[x]>ver)x=fa[x];
		ll now=2e9+1e8;
		int l=0,r=vec[x].size()-1;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(vec[x][mid].ver>ver)now=chkmin(now,vec[x][mid].ans),l=mid+1;
			else r=mid-1;
		}return lastans=now;
	}
	void init()
	{memset(dep,0,sizeof(dep)),memset(fa,0,sizeof(fa));}
}
void Init()
{
	memset(book,0,sizeof(book));
	memset(head,0,sizeof(head));
	t=Et=lastans=0;
}
/*bool cmp(qwq a,qwq b)
{return a.p>b.p;}
bool cmp3(qwq a,qwq b)
{return a.id<b.id;}*/
bool cmp2(node a,node b)
{return a.h>b.h;}
int main()
{
	using namespace Path;
	using namespace Uset;
	int x,y,o,cas;ll z;
	read(cas);
	while(cas--)
	{
		//cerr<<"ok"<<endl;
		Init();
		read(n),read(m);
		f(i,1,m)
		{
			read(x),read(y),read(z),read(o);
			add(x,y,z,o);
		}dijkstra(),init();
		f(i,1,n)vec[i].clear(),vec[i].push_back((qwq){inf,dis[i]});
		sort(E+1,E+Et+1,cmp2);
		f(i,1,m)merge(E[i].u,E[i].v,E[i].h);
		read(Q),read(K),read(maxA);
		//f(i,1,n)printf("%d\n",dep[i]);
/*		f(i,1,Q)read(q[i].v),read(q[i].p),q[i].id=i;
		sort(q+1,q+Q+1,cmp);*/
//		cerr<<mindis[1]<<endl;
		//cerr<<"a"<<endl;
		f(i,1,Q)
		{
			read(x),read(y);
			x=(x+K*lastans-1)%n+1,y=(y+K*lastans)%(maxA+1);
			printf("%lld\n",solve(x,y));
		}
/*		f(i,1,Q)
		{
			while(E[tp].h>q[i].p)
			{
				//cerr<<tp<<" ";
				merge(E[tp].u,E[tp].v);
				//x=find(E[tp].u);
				//mindis[x]=chkmin(mindis[x],chkmin(mindis[E[tp].u],mindis[E[tp].v]));
				++tp;
				if(tp>Et)break;
			}
			ans[q[i].id]=mindis[find(q[i].v)];
		}//f(i,1,n)printf("fa %d %d\n",mindis[i],fa[i]);
//		cerr<<"aok"<<endl;		
		//sort(q+1,q+Q+1,cmp3);
//		cerr<<"bok"<<endl;		
		f(i,1,Q)printf("%lld\n",ans[i]);*/
		//cerr<<clock()<<endl;
	}
}

评测结果