代码

#include<bits/stdc++.h>
#define ll long long
#define make_pair(a,b) {a,b}
using namespace std;
using namespace std;
namespace FAST_IO
{
	char buf[1<<20],*p1,*p2,ch;
	int x,f;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
	inline int read(){
		x=f=0,ch=getchar();
		while(!isdigit(ch))
		{
			if(ch=='-')f=1;
			ch=getchar();
		}
		do x=(x<<1)+(x<<3)+(ch^48),ch=getchar();while(isdigit(ch));
		return f?-x:x;
	}
	inline void Write(register const int &p)
	{
		if(9<p)Write(p/10);
		putchar(p%10|48);
	}
	inline void write(register const int &p){if(p<0)putchar('-'),Write(-p);else Write(p);}
}
using FAST_IO::read;
using FAST_IO::write;
template<typename Key>
struct priority__queue{
	private:
		int size;
		Key h[1000005];
		inline void up(register const int &x)
		{		
			if(h[x]<h[x>>1])
			{
				swap(h[x],h[x>>1]);
				up(x>>1);
			} 
		}
		inline void down(register const int &x)
		{	
			int t=x;
			if((x<<1)<=size&&h[x<<1]<h[t])
			{
				t=(x<<1);
			} 
			if((x<<1|1)<=size&&h[x<<1|1]<h[t])
			{
				t=(x<<1|1);
			} 
			if(x!=t)
			{
				swap(h[x],h[t]);
				down(t);
			} 
		}
	public:
		inline void push(Key a)
		{
			h[size=-~size]=a;
			up(size);
		}
		inline Key top()
		{
			return h[1];
		}
		inline void pop()
		{
			h[1]=h[size];
			size=~-size;
			down(1);
		}
		inline void delate(register const int k)
		{
			h[k]=h[size];
			size=~-size;
			down(k);
		}
		inline bool empty()
		{
			return !size;
		}
};
int n,m,cnt,head[800001],tot;
ll d[800001],vis[800001],father[800001],min1[800001],value[800001],grand[800001][27];
ll Q,K,S;
struct node1{
	int u,v;
	ll w;
}edge[1600001]; 
inline bool cmp(node1 x,node1 y)
{
	return x.w>y.w;
}
struct node2{
	int v,next;
	ll dis;
}E[1600001];
inline void add_edge(register const int &u,register const int &v,register const ll &dis)
{
	E[tot=-~tot].next=head[u];
	E[tot].v=v;
	E[tot].dis=dis;
	head[u]=tot;
}
priority_queue<pair<ll,int>>q;
inline void dijkstra()
{
	memset(vis,0,sizeof(vis));
	memset(d,0x3f,sizeof(d));
	d[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u])
		{
			continue;
		}
		vis[u]=1;
		for(int i=head[u];i;i=E[i].next)
		{
			int v=E[i].v;
			if(d[u]+E[i].dis<d[v])
			{
				d[v]=d[u]+E[i].dis;
				q.push(make_pair(-d[v],v));
			}
		}
	}
}
inline void dfs(register const int &u)
{
	min1[u]=d[u];
	for(register int i=head[u];i;i=E[i].next)
	{
		register int vv=E[i].v;
		grand[vv][0]=u;
		dfs(vv);
		min1[u]=min(min1[u],min1[vv]);
	}
}
inline int find(register const int &x)
{
	if(x!=father[x])
	{
		father[x]=find(father[x]);
	}
	return father[x];
}
inline void kruskal()
{
	memset(head,0,sizeof(head));
	tot=1;
	sort(edge+1,edge+1+m,cmp);
	for(register int i(1);i<=n;i=-~i)
	{
		father[i]=i;
	}
	for(register int i(1);i<=m;i=-~i)
	{
		register int uu=find(edge[i].u),vv=find(edge[i].v);
		if(uu!=vv)
		{
			value[cnt=-~cnt]=edge[i].w;
			father[uu]=father[vv]=father[cnt]=cnt;
			add_edge(cnt,uu,0);
			add_edge(cnt,vv,0);
		}
	}
	dfs(cnt);
}
int main()
{
	int T=read();
	while(T--)
	{
		tot=1;
		memset(head,0,sizeof(head));
		memset(grand,0,sizeof(grand));
		memset(min1,0x3f,sizeof(min1));
		n=read(),m=read();
		cnt=n;
		for(register int i(1);i<=m;i=-~i)
		{
			int u=read(),v=read(),l=read(),a=read();
			add_edge(u,v,l);
			add_edge(v,u,l);
			edge[i].u=u;
			edge[i].v=v;
			edge[i].w=a;
		}
		dijkstra(); 
		kruskal();
		for(register int i(1);(1<<i)<=cnt;i=-~i)
		{
			for(register int j(1);j<=cnt;j=-~j)
			{
				grand[j][i]=grand[grand[j][i-1]][i-1];
			}
		}
		ll l=0;
		Q=read(),K=read(),S=read();
		while(Q--)
		{
			int v1=read(),u1=read();
			v1=(v1+K*l-1)%n+1;
			u1=(u1+K*l)%(S+1);
			for(register int j(22);j>=0;j=~-j)
			{
				if(grand[v1][j]&&value[grand[v1][j]]>u1)
				{
					v1=grand[v1][j];
				}
			}
			l=min1[v1];
			printf("%lld\n",l);
		}
	}
	return 0;
} 

评测结果