代码

#include <cstdio>
#include <cctype> 
#include <algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define init(a) fo(ii,1,n)a[ii]=inf
#define clear(a) fo(ii,1,n)a[ii]=0
#define rep(i,x) for(edge *i=x; i; i=i->ne)
#define MIN(x,y) x=min(x,y)
using namespace std;
typedef long long ll;

const int N=2e5+1,M=N<<2;
const ll inf=0x7FFFFFFF;
int T,i,n,m,u,v,l,a,Q,K,S,v0,p0,p,st,en,q[10*N],x;
bool onekind,exist[N],vis[N],tree;
ll dis[N],ans;
struct edge
{
	int to,a;
	ll l;
	edge *ne;
	edge(int to,ll l,int a,edge *ne) : to(to), l(l), a(a), ne(ne){}
}*fin[N];

inline void read(int &x)
{
	char ch=getchar(); x=0;
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
}

inline void link(int x,int y)
{
	fin[x]=new edge(y,l,a,fin[x]);
}

void spfa(int x)
{
	int ii,y;
	init(dis);    dis[x]=0;
	clear(exist); exist[x]=1;
	st=0; q[en=1]=x;
	while(st<en)
	{
		x=q[++st];
		rep(i,fin[x])
		{
			y=i->to;
			if(dis[y]<=dis[x]+i->l) continue;
			dis[y]=dis[x]+i->l;
			if(!exist[y])
			{
				exist[y]=1; q[++en]=y;
				if(dis[y]<dis[q[st+1]]) swap(q[en],q[st+1]);
			}
		}
		exist[x]=0;
	}
}

void flood(int x)
{
	vis[x]=1;
	rep(i,fin[x]) 
		if(i->a>p)
		{
			int y=i->to;
			if(!vis[y]) flood(y);
		}
}//get visitable vertexes

int fa[N],anc[N][18],low[N][18];
ll len[N];
void dfs(int x)
{
	int i,f;
	f=anc[x][0]=fa[x];
	fo(i,1,17)
	{
		if(!f) break;
		low[x][i]=min(low[x][i-1],low[f][i-1]);
		f=anc[x][i]=anc[f][i-1];
	}
	
	rep(i,fin[x])
	{
		int y=i->to;
		if(y==fa[x]) continue;
		fa[y]=x; low[y][0]=i->a; 
		len[y]=len[x]+i->l; dfs(y);
	}
}

int main()
{
	for(read(T);T;T--)
	{
		read(n); read(m); 
		onekind=1; tree=(m==n-1);
		fo(i,1,m)
		{
			read(u); read(v); read(l); read(a);
			link(u,v); link(v,u);
			onekind&=(a==1);
		}
		read(Q); read(K); read(S);
		
		if(onekind) spfa(1);
		else
		if(tree) dfs(1);
		
		fo(i,1,Q) 
		{
			read(v0); read(p0);
			
			if(onekind)
			{
				printf("%lld\n",(p0>0)*dis[v0]);
				continue;
			}
			
			v=(v0+K*ans-1)%n+1;
			p=(p0+K*ans)%(S+1);
			int ii;
			
			if(tree)
			{
				fd(ii,17,0) if( anc[v][ii] && low[v][ii]>p ) v=anc[v][ii];
				printf("%lld\n",ans=len[v]);
				continue;
			}
			
			clear(vis);
			flood(v);	
			spfa(1);
			ans=inf;
			fo(x,1,n) if(vis[x]) MIN(ans,dis[x]);
			printf("%lld\n",ans);
		}	
	}
}

评测结果