代码

#include<cstdio>
#include<algorithm>
#include<set>
#include<queue>
#include<cstring>
#include<cmath>
#include<ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define REP(i,a,b) for(int i=a;i<=b;++i)
typedef long long ll;

using namespace std;

void File(){
	freopen("return.in","r",stdin);
	freopen("return.out","w",stdout);
}

template<typename T>
void read(T &x){
    T _=0,mul=1;
    char __=getchar();
    while(!isdigit(__)){
        if(__=='-')mul=-1;
        __=getchar();
    }
    while(isdigit(__))_=(_<<1)+(_<<3)+(__^'0'),__=getchar();
    x=_*mul;
}

template<typename T>
void write(T x,char c){
    if(x==0){
        putchar('0');
        putchar(c);
        return;
    }
    if(x<0){putchar('-');x=-x;}
    ll le=1,y=10;
    while(y<=x)y=(y<<3)+(y<<1),++le;
    while(le--){
        y/=10;
        putchar(x/y+48);
        x%=y;
    }
    putchar(c);
}

const int maxn=2e5+10;
const int maxm=4e5+10;
int T,n,m,q,K,S;
int beg[maxn],las[maxm<<1],to[maxm<<1],len[maxm<<1],h[maxm<<1],cnte;

void add(int u,int v,int l,int a){
	las[++cnte]=beg[u];
	beg[u]=cnte;
	to[cnte]=v;
	len[cnte]=l;
	h[cnte]=a;
}

int dis[maxn];
bool vis[maxn];
void spfa(){
	memset(dis,63,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[1]=0;
	deque<int>qu;
	qu.push_back(1);
	ll sum=0;
	while(qu.size()){
		int u=qu.front();
		while(dis[u]>(sum/qu.size())){
			qu.pop_front();
			qu.push_back(u);
			u=qu.front();
		}
		qu.pop_front();
		sum-=dis[u]; vis[u]=0;
		for(int i=beg[u];i;i=las[i]){
			if(dis[u]+len[i]<dis[to[i]]){
				dis[to[i]]=dis[u]+len[i];
				if(!vis[to[i]]){
					vis[to[i]]=1;
					if(qu.empty() || dis[to[i]]>dis[qu.back()])qu.push_back(to[i]);
					else qu.push_front(to[i]);
					sum+=dis[to[i]];
				}
			}
		}
	}
}

struct node{
	int v0,p0,id;
	bool operator < (const node & tt) const{
		return p0<tt.p0;
	}
}d[maxm];

int ans[maxm],sum[maxn];
multiset<node>s1;
set<int>s2;
set<int>::iterator it;

int main(){
	//File();
	read(T);
	while(T--){
		bool sub1=true,sub2=true,sub3=true;
		cnte=1;
		memset(beg,0,sizeof(beg));
		s1.clear(); s2.clear();
		read(n); read(m);
		if(m!=n-1)sub2=sub3=false;
		int u,v,l,a;
		REP(i,1,m){
			read(u); read(v); read(l); read(a);
			add(u,v,l,a);
			add(v,u,l,a);
			if(a!=1)sub1=false;
			if(u+1!=v)sub2=false;
			sum[i+1]=sum[i]+l;
		}
		read(q); read(K); read(S);
		if(sub1){
			spfa();
			int lasans=0,v0,p0;
			REP(i,1,q){
				read(v0); read(p0);
				v0=(v0+K*lasans-1)%n+1;
				p0=(p0+K*lasans)%(S+1);
				if(p0>=1)lasans=dis[v0];
				else lasans=0;
				write(lasans,'\n');
			}
			return 0;
		}
		if(sub2){
			int v0,p0;
			REP(i,1,q){
				read(v0); read(p0);
				v0=(v0-1)%n+1;
				p0=p0%(S+1);
				d[i]=(node){v0,p0,i};
			}
			sort(d+1,d+q+1);
			for(int i=2;i<=cnte;i+=2)
				s1.insert((node){to[i],h[i],0});
			REP(i,1,q){
				int hei=d[i].p0;
				while(s1.size() && s1.begin()->p0<=hei){
					s2.insert(s1.begin()->v0);
					s1.erase(s1.begin());
				}
				it=s2.upper_bound(d[i].v0);
				if(it==s2.begin())ans[d[i].id]=0;
				else{
					--it;
					ans[d[i].id]=sum[*it];
				}
			}
			REP(i,1,q)write(ans[i],'\n');
		}
	}
	return 0;
}

评测结果