代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=2e5+505,maxm=4e5+505;
#define inf 0x3f3f3f3f
//最短路
int head[maxn],num_edge;
struct Edge{int next,to,v;};
Edge /*):*/ed[maxm*2];//:( && TAT
void add_edge(int from,int to,int v){
	ed[++num_edge].next=head[from];
	ed[num_edge].to=to;
	ed[num_edge].v=v;
	head[from]=num_edge;
}
#define pii pair<int,int>
int d[maxn];
priority_queue<pii,vector<pii>,greater<pii> >q;
void Dj(int s){
	memset(d,0x3f,sizeof(d));
	d[s]=0,q.push(pii(0,s));
	while(!q.empty()){
		pii h=q.top();q.pop();
		int k=h.second;
		if(h.first!=d[k])continue;
		for(int i=head[k];i;i=ed[i].next){
			int to=ed[i].to,e=d[k]+ed[i].v;
			if(d[to]>e){
				d[to]=e;
				q.push(pii(e,to));
			}
		}
	}
}
//Kruskal重构树
struct node{
	bool leaf;
	int hi,min;//hi:海拔,min:s to point1 min 
	node*lc,*rc,*fa;
}pool[maxm+maxn];//sizeof?
node*top=pool;
#define new_node (++top)
node*ontree[maxn];

int f[maxn],size[maxn];
int find(int r){
	if(r==f[r])return r;
	return f[r]=find(f[r]);
}
inline void unite(int x,int y,int val){
	int fx=find(x),fy=find(y);
	if(fx==fy)return;
	//cout<<x<<'|'<<y<<endl;
	if(size[fx]<size[fy])swap(fx,fy)/*,swap(x,y)*/;
	f[fy]=fx,size[fx]+=size[fy];
	ontree[fx]->fa=new_node,ontree[fy]->fa=top;
	top->lc=ontree[fx],top->rc=ontree[fy];
	top->hi=val,top->min=min(ontree[fx]->min,ontree[fy]->min);
	ontree[fx]=top;
}
struct EDED{int u,v,l,a;}edge[maxm];
bool cmp(EDED a,EDED b){return a.a>b.a;}
void Kruskal(int m){
	sort(edge+1,edge+m+1,cmp);
	for(int i=1;i<=m;i++){
		unite(edge[i].u,edge[i].v,edge[i].a);
	}
}
//倍增
int ffa[maxm+maxn][35];
int query(int st,int dep){
	int i=st;
	for(int b=31;b>=0;b--){
		if(ffa[i][b]<=0)continue;
		if((pool+ffa[i][b])->hi>dep)
			i=ffa[i][b];
	}
	return (pool+i)->min;
} 
#define cl(a) memset(a,0,sizeof(a))
//#define ca(a,...) (cl(a),ca(...))
int work(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		EDED&ee=edge[i];
		scanf("%d%d%d%d",&ee.u,&ee.v,&ee.l,&ee.a);
		add_edge(ee.u,ee.v,ee.l);
		add_edge(ee.v,ee.u,ee.l);
	}
	Dj(1);
	//Kruskal初始化
	for(int i=1;i<=n;i++)f[i]=i,size[i]=1;
	for(int i=1;i<=n;i++){
		new_node;
		top->hi =inf;
		top->min=d[i];
		top->leaf=1;
		ontree[i]=top;
	}
	
	Kruskal(m);
	/*debug 
	for(int i=1;i<=n;i++)cout<<d[i]<<' ';cout<<endl;
	cout<<top-pool<<endl;
	for(int i=1;i<=n;i++)cout<<f[i]<<' ';cout<<endl;
	for(int i=1;i<=n;i++)cout<<ontree[i]-pool<<' ';cout<<endl;
	for(node*i=pool+1;i<=top;i++)
		if(i->fa==NULL)cout<<"Null ";else cout<<i->fa-pool<<' ';cout<<endl;
	for(node*i=pool+1;i<=top;i++)
		cout<<i->hi<<' ';cout<<endl;
	cout<<"-----\n";*/
	//倍增初始化
	int treesize=top-pool;
	for(int i=1;i<treesize;i++)ffa[i][0]=pool[i].fa-pool;//,cout<<ffa[i][0]<<' ';cout<<endl;//
	for(int b=1;b<32;b++){
		for(int i=1;i<treesize;i++){
			ffa[i][b]=ffa[ffa[i][b-1]][b-1];//,cout<<ffa[i][b]<<' ';//
		}//cout<<endl;
	}
	
	int q,k,s,lastans=0;
	scanf("%d%d%d",&q,&k,&s);
	for(int i=1;i<=q;i++){
		int v0,p0;
		scanf("%d%d",&v0,&p0);
		int v=(v0+k*lastans-1)%n+1;
		int p=(p0+k*lastans)%(s+1);
		lastans=query(v,p);
		printf("%d\n",lastans);
	}
	cl(head),cl(ed),num_edge=0,cl(d);
	cl(pool),top=pool,cl(ontree),cl(f),cl(size),cl(edge),cl(ffa);
	return 0;
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--)work();
}

评测结果