代码

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define _(d) while(d((ch=getchar()-48)>=0))
inline int get(){
	char ch;_(!);int x=ch;
	_() x=(x<<3)+(x<<1)+ch;
	return x;
}
const int N=200001,M=800001,inf=0x7f7f7f7f;
int n,m,Q,tt,h[N],to[M],nx[M],c[M],d[N],in[N],p[N],t[N],r[N],v[N];
vector<pair<int,int> >vt[N];
struct info{
	int u,v,l,a;
	void init(){
		u=get(),v=get(),l=get(),a=get();
		to[++tt]=v,nx[tt]=h[u],h[u]=tt,c[tt]=l;
		to[++tt]=u,nx[tt]=h[v],h[v]=tt,c[tt]=l;
	}
	bool operator<(const info &r)const{
		return a>r.a;
	}
}e[M];
struct ele{
	int d,p;
	ele(int d=0,int p=0):d(d),p(p){}
	bool operator<(const ele &r)const{
		return d>r.d;
	}
};priority_queue<ele>q;
void dijkstra(){
	memset(d+1,0x7f,n<<2);
	q.push(ele(d[1]=0,1));
	while(!q.empty()){
		int x=q.top().p;q.pop();
		for(int i=h[x];i;i=nx[i])
			if(d[x]+c[i]<d[to[i]])
				q.push(ele(d[to[i]]=d[x]+c[i],to[i]));
		while(!q.empty()&&d[q.top().p]!=q.top().d) q.pop();
	} 
}
int fnd(int x){
	while(x!=p[x]) x=p[x];
	return x;
}
void uni(int a,int b,int u){
	if(r[a]<r[b]) swap(a,b);
	if(r[a]==r[b]) ++r[a];
	p[b]=a,t[b]=u,v[a]=min(v[a],v[b]);
	vt[a].push_back(make_pair(u,v[b]));
}
int qry(int x,int s){
	int u;
	for(u=x;u!=p[u];u=p[u])
		if(t[u]<=s) break;
	return min(d[u],upper_bound(vt[u].begin(),vt[u].end(),make_pair(s,inf))->second);
}
int main(){
	for(int T=get();T--;){
		n=get(),m=get(),tt=0;
		for(int i=1;i<=n;++i) h[i]=r[i]=t[i]=0,p[i]=i;
		for(int i=1;i<=m;++i) e[i].init();
		dijkstra();
		memcpy(v+1,d+1,n<<2);
		for(int i=1;i<=n;++i)
			vt[i].clear(),vt[i].push_back(make_pair(inf,inf));
		sort(e+1,e+m+1);
		for(int i=1;i<=m;++i)
			uni(fnd(e[i].u),fnd(e[i].v),e[i].a);
		for(int i=1;i<=n;++i){
			sort(vt[i].begin(),vt[i].end());
			for(int j=vt[i].size()-2;j>=0;--j)
				vt[i][j].second=min(vt[i][j].second,vt[i][j+1].second);
		}
		int Q=get(),K=get(),S=get()+1,lan=0;
		for(int i=1,v,p;i<=Q;++i){
			v=(get()+lan*K-1)%n+1;
			p=(get()+lan*K)%S;
			printf("%d\n",lan=qry(v,p));
		}
	}
	return 0;
}

评测结果