代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define sp cout<<"---------------------------------------------------"<<endl
inline int read(){
	  int x=0,f=1;char s=getchar();
	  while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
	  while(isdigit(s)){x=(x<<3)+(x<<1)+(s-'0');s=getchar();}
	  return x*f;
}
int cnt,to[800010],head[800010],nxt[800010],len[800010],h[800010];
int lian[2500],flian[2500];
int n,m,Q,s,k;
inline void add(int x,int y,int z,int w){
	  nxt[++cnt]=head[x];
	  head[x]=cnt;
	  to[cnt]=y;
	  len[cnt]=z;
	  h[cnt]=w;
	  if(n<=1500)lian[x]=cnt;
	  nxt[++cnt]=head[y];
	  head[y]=cnt;
	  to[cnt]=x;
	  len[cnt]=z;
	  h[cnt]=w;
	  if(n<=1500)flian[y]=cnt;
	  return;
}
priority_queue<pair<int,int> >q;
int d[200010],vis[200010];
inline void deal(){
	  int i,j,ans=0;
	  memset(d,0x3f,sizeof(d));
	  d[1]=0;
	  q.push(make_pair(0,1));
	  while(!q.empty()){
	    int x=q.top().second;
		q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(i=head[x];i;i=nxt[i]){
		  int y=to[i];
		  if(d[x]+len[i]<d[y]){
		  	d[y]=d[x]+len[i];
		  	q.push(make_pair(-d[y],y));
		  }
	    }
	  }
	  int v,p;
	  for(i=1;i<=Q;i++){
	  	v=read(),p=read();
	  	v=(v+ans*k-1)%n+1;
	  	p=(p+k*ans)%(s+1);
	  	if(p>=1)ans=d[v];
	  	  else ans=0;
	  	printf("%d\n",ans);
	  }
	  return;
}
inline void deallian(){
	  int i,j,v,p,ans=0;
	  memset(d,0,sizeof(d));
	  int x=1,y;
	  while(x!=n){
	  	i=lian[x];
	  	y=to[i];
	  	d[y]=d[x]+len[i];
	  	x=y;
	  }
	  for(j=1;j<=Q;j++){
	  	v=read(),p=read();
	  	v=(v+ans*k-1)%n+1;
	  	p=(p+k*ans)%(s+1);
	  	ans=0;
	  	x=v;
	  	while(x!=1){
	  	  i=flian[x];
	  	  y=to[i];
	  	  if(h[i]<=p){
			ans=d[x];
			break;
		  }
	  	  x=y;
	    }
	    printf("%d\n",ans);
	  }
	  return;
}
const int Log=19;
int per[200010][Log+3][2],dep[200010];
inline void dfs(int x,int fa,int id){
	  dep[x]=dep[fa]+1;
	  if(fa==0)per[x][0][1]=0;
	    else per[x][0][1]=h[id];
	  per[x][0][0]=fa;
	  for(int i=1;(1<<i)<=dep[x];i++){
	  	per[x][i][0]=per[per[x][i-1][0]][i-1][0];
	  	per[x][i][1]=min(per[x][i-1][1],per[per[x][i-1][0]][i-1][1]);
	  }
	  for(int i=head[x];i;i=nxt[i])
	    if(to[i]!=fa)
	      dfs(to[i],x,i);
	  return;
}
inline void dfs2(int x,int fa){
	  for(int i=head[x];i;i=nxt[i])
	    if(to[i]!=fa){
	      d[to[i]]=d[x]+len[i];
	      dfs2(to[i],x);
	    }
	  return;
}
inline int work(int v,int p){
	  int i,j;
	  for(i=Log;i>=0;i--)
	    if(per[v][i][0]>0&&per[v][i][1]>p)
	      v=per[v][i][0];
	  return d[v];
}
inline void dealtree(){
	  int i,j,ans=0,v,p;
	  for(i=1;i<=n;i++)
	    for(j=0;j<=Log+1;j++){
	      per[i][j][0]=0;
	      per[i][j][1]=0x3f3f3f3f;
	    }
	  dfs(1,0,0);
	  memset(d,0,sizeof(d));
	  dfs2(1,0);
	  for(int _=1;_<=Q;_++){
	  	v=read(),p=read();
	  	v=(v+ans*k-1)%n+1;
	  	p=(p+k*ans)%(s+1);
	  	ans=work(v,p);
	  	printf("%d\n",ans);
	  }
	  return;
}
int main(){
      freopen("return.in","r",stdin);
	  freopen("return.out","w",stdout);
	  int i,j,t;
	  t=read();
	  while(t--){
	  	n=read(),m=read();
	  	cnt=0;
	  	for(i=1;i<=m;i++){
	  	  int x,y,z,w;
	  	  x=read(),y=read(),z=read(),w=read();
	  	  add(x,y,z,w);
	    }
	    Q=read(),k=read(),s=read();
	    if(m==n-1){
		  if(n<=1500)deallian();
		    else dealtree();
		}else deal();	    
	  }
	  return 0;
}

评测结果