代码

#include <cstdio>
#include <cstring>
#include <iostream>
#define oo 2139062143
#define fo(i,x,y) for (ll i=(x);i<=(y);++i)
#define fd(i,x,y) for (ll i=(x);i>=(y);--i)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PI;
const ll N=200200,M=400400*2,Q=100100;
ll n,m,q,k,s;
ll to[M],las[N],nex[M],len[M],a[M];
struct qery{
	ll v,p;
	ll id;
}qu[Q];
ll tot;
ll ans[Q];
void link(ll x,ll y,ll l,ll aa)
{
	to[++tot]=y,nex[tot]=las[x],las[x]=tot,len[tot]=l,a[tot]=aa;
}
ll lastans,T;
ll dis[N],d[N*10];
ll hd,tl;
ll vis[N];
void spfa()
{
	memset(vis,0,sizeof vis);
	memset(dis,127,sizeof dis);dis[1]=0;
	hd=0,d[tl=1]=1,vis[1]=1;
	while(hd++<tl)
	{
		ll nw=d[hd];
		for(ll tp=las[nw];tp;tp=tp[nex])
		if(tp[to][dis]>dis[nw]+len[tp])
		{
			tp[to][dis]=dis[nw]+len[tp];
			if(!vis[tp[to]])
			{
				vis[tp[to]]=1;
				d[++tl]=to[tp];
			}
		}
		vis[nw]=0;
	}
}
ll fa[N][18],mn[N][18];
void dfs(ll x,ll d)
{
	dis[x]=d;
	for(ll tp=las[x];tp;tp=tp[nex])
	if(tp[to]!=fa[x][0])
	{
		fa[tp[to]][0]=x,mn[tp[to]][0]=tp[a];
		dfs(tp[to],d+tp[len]);
	}
}
int main()
{
	//freopen("return.in","r",stdin);
	//freopen("return.out","w",stdout);
//	freopen("D:/LiuYuanHao/a4.in","r",stdin);
//	freopen("D:/LiuYuanHao/a.out","w",stdout);
	scanf("%lld",&T);
	while(T--)
	{
		tot=0;
		ll flags=1;
		lastans=0;
		memset(ans,0,sizeof ans);
		memset(dis,127,sizeof dis);
		//clear
		scanf("%lld%lld",&n,&m);
		fo(i,1,m)
		{
			ll u,v,l,a;
			scanf("%lld%lld%lld%lld",&u,&v,&l,&a);
			link(u,v,l,a),link(v,u,l,a);
			if(a!=1) flags=0;
		}
		scanf("%lld%lld%lld",&q,&k,&s);
		fo(i,1,q)
		{
			scanf("%lld%lld",&qu[i].v,&qu[i].p);
			qu[i].id=i;
		}
		if(flags)
		{
			spfa();
			fo(i,1,q)
				if(qu[i].p==1)
					ans[qu[i].id]=dis[qu[i].v];
			fo(i,1,q) printf("%lld\n",ans[i]);
			continue;
		}
		if(m==n-1)
		{
			dis[1]=dis[0]=0;
			dfs(1,0);
			fo(l,1,17) fo(i,1,n) 
				fa[i][l]=fa[fa[i][l-1]][l-1],mn[i][l]=min(mn[i][l-1],mn[fa[i][l-1]][l-1]);
			fo(i,1,q)
			{
				qu[i].v=(qu[i].v+k*lastans-1)%n+1;
				qu[i].p=(qu[i].p+k*lastans)%(s+1);
				ll nw=qu[i].v;
				fd(l,17,0) if(mn[nw][l]>qu[i].p)
					nw=fa[nw][l];
				printf("%lld\n",dis[nw]);
				lastans=dis[nw];
			}
			continue;
		}
	}
	return 0;
}

评测结果