代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define mem(x) (memset(x,0,sizeof(x)))
typedef long long ll;
const int maxn=200020,maxm=400040;
struct edge1{
	int u,v,w;
	bool operator<(const edge1 e)const{
		return w>e.w;
	}
}e1[maxm];
struct edge2{
	int v,w,nxt;
}e2[maxm<<1],e3[maxn<<1];
struct state{
	int u;ll dis;
	bool operator<(const state s)const{
		return dis>s.dis;
	}
};
int t,n,m,q,k,s;
int el2,el3,head2[maxn],head3[maxn<<1];
int u_fa[maxn<<1],cnt;
ll lastans,dis[maxn],w[maxn<<1],mind[maxn<<1],fa[maxn<<1][21];
priority_queue<state> pq;
inline void add2(int u,int v,int w){
	e2[++el2]=(edge2){v,w,head2[u]};head2[u]=el2;
}
inline void add3(int u,int v){
	e3[++el3]=(edge2){v,0,head3[u]};head3[u]=el3;
}
void dijkstra(){
	while(!pq.empty()) pq.pop();
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;
	pq.push((state){1,0});
	while(!pq.empty()){
		int u=pq.top().u;ll d=pq.top().dis;pq.pop();
		if(d>dis[u]) continue;
		for(int i=head2[u];i;i=e2[i].nxt){
			int v=e2[i].v;
			if(dis[u]+e2[i].w<dis[v]) pq.push((state){v,dis[v]=dis[u]+e2[i].w});
		}
	}
}
int getfa(int x){
	return x==u_fa[x]?x:u_fa[x]=getfa(u_fa[x]);
}
void kruskal(){
	sort(e1+1,e1+m+1);
	for(int i=1;i<=n*2-1;i++) u_fa[i]=i;
	for(int i=1;i<=n;i++) w[i]=-1e18;
	cnt=n;
	for(int i=1;i<=m;i++){
		int u=e1[i].u,v=e1[i].v;
		u=getfa(u);v=getfa(v);
		if(u==v) continue;
		w[++cnt]=e1[i].w;
		u_fa[u]=u_fa[v]=cnt;
		add3(cnt,u);add3(cnt,v);
	}
}
void dfs(int u){
	mind[u]=u>n?1e18:dis[u];
	for(int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=head3[u];i;i=e3[i].nxt){
		int v=e3[i].v;
		fa[v][0]=u;
		dfs(v);
		mind[u]=min(mind[u],mind[v]);
	}
}
ll calc(ll st,ll p){
	for(int i=20;~i;i--)
		if(w[fa[st][i]]>p) st=fa[st][i];
	return mind[st];
}
int main(){
	scanf("%d",&t);
	while(t--){
		mem(e1);mem(e2);mem(e3);mem(head2);mem(head3);mem(w);mem(mind);mem(fa);
		w[lastans=el2=el3=cnt=0]=-1e18;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++){
			int u,v,w1,w2;
			scanf("%d%d%d%d",&u,&v,&w1,&w2);
			e1[i]=(edge1){u,v,w2};
			add2(u,v,w1);add2(v,u,w1);
		}
		dijkstra();
		kruskal();
		fa[cnt][0]=0;
		dfs(cnt);
		scanf("%d%d%d",&q,&k,&s);
		for(int i=1;i<=q;i++){
			int st,p;
			scanf("%d%d",&st,&p);
			st=(st+k*lastans-1)%n+1;
			p=(p+k*lastans)%(s+1);
			printf("%lld\n",lastans=calc(st,p));
		}
	}
}

评测结果