代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<deque>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
typedef long long ll;
using namespace std;

int T,n,m,nex[8010],st[1510],dist[8010],high[8010],to[8010],dis[1510],Q,k,s;
bool vis[1510],reach[1510];

int fa[1510],sum[1510],hi[1510];

void link(int x,int y,int D,int H){
	static int t;
	nex[++t]=st[x],to[t]=y,st[x]=t,dist[t]=D,high[t]=H;
}

deque<int>q;

int spfa(int s){
	
	memset(dis,0x1f,sizeof(dis));
	dis[s]=0;
	memset(vis,0,sizeof(vis));
	q.clear();
	q.push_back(s);vis[s]=1;
	int k,x,y;
	
	deque<int>::iterator ite;
	while(!q.empty()){
		x=q.front(),q.pop_front(),vis[x]=0;
		
		for(k=st[x];k!=0;k=nex[k]){
			y=to[k];
			
			if(dis[x]+dist[k]<dis[y]){
				dis[y]=dis[x]+dist[k];
				
				if(!vis[y]){
					vis[y]=1; 
					q.push_back(y);
					
					if(q.size()>1&&dis[*(ite=q.begin()+1)]>dis[y])
						swap(*ite,*(q.end()-1));   
				}
			}
		}
	}
}

void prepare(int top,int fat){
	for(int k=st[top];k;k=nex[k]){
		if(to[k]==fat)continue;
		fa[to[k]]=top;
		sum[to[k]]=sum[top]+dist[k];
		hi[to[k]]=high[k];
		prepare(to[k],top);
	}
}

int Getans(int st,int cov){
	if(st==1)return 0;
	if(hi[st]<=cov)return sum[st];
	return Getans(fa[st],cov); 
}

int data[1510];
void bfs(int s,int Minh){
	int h=0,t=1;data[1]=s,memset(reach,0,sizeof reach);
	reach[s]=1;
	while(h<t){
		++h;
		for(int k=st[data[h]];k;k=nex[k])
			if(!reach[to[k]]&&high[k]>Minh){
				reach[to[k]]=1;
				data[++t]=to[k];
			}
	}
}

int main(){
//	freopen("1_init.in","r",stdin);freopen("1_out.out","w",stdout);
	freopen("return.in","r",stdin);freopen("return.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		bool P=0;
		memset(nex,0,sizeof nex),memset(st,0,sizeof st),memset(dist,0,sizeof dist),memset(high,0,sizeof high);
		memset(sum,0,sizeof sum),memset(fa,0,sizeof fa),memset(hi,0,sizeof hi);
		if(m+1==n)P=1;
		
		while(m--){
			int x,y,z,l;
			cin>>x>>y>>z>>l;
			link(x,y,z,l),link(y,x,z,l);
		}
		
		cin>>Q>>k>>s;
		int la=0;
		if(!P){
			if(n>5000){
				spfa(1);
				while(Q--){
					int st,cov;
					cin>>st>>cov;
					st=(st+k*la-1)%n+1;
					cov=(cov+k*la)%(s+1);
					if(cov<1)cout<<(la=0)<<"\n";
					else cout<<(la=dis[st])<<"\n";
				}
				return 0;
			}
			while(Q--){
				int st,cov;
				cin>>st>>cov;
				st=(st+k*la-1)%n+1;
				cov=(cov+k*la)%(s+1);
				bfs(st,cov);
				spfa(1);
				int ans=1e9;
				rep(i,1,n)
					if(reach[i])ans=min(ans,dis[i]);
				cout<<(la=ans)<<"\n";
			}
		}
		
		else{
			prepare(1,0);
			while(Q--){
				int st,cov;
				cin>>st>>cov;
				st=(st+k*la-1)%n+1;
				cov=(cov+k*la)%(s+1);
				cout<<(la=Getans(st,cov))<<"\n";
			}
		}
	}
}

评测结果