代码

#include<cstdio>
//#include<iostream>
#include<cstring>
//#include<windows.h>
#include<algorithm>
#include<cmath>
#include<queue>
#define MN 400005
#define MM 18000005 
using namespace std;
int T,n,m,num,Q,k,s,qsum,tt,tot,dis[MN],head[MN],x[MN],y[MN],len[MN],v[MN],id[MN],ls[MM],rs[MM],rt[MN],nnum[MN];bool vis[MN];
struct node{
	int x,y;
	friend bool operator<(node x,node y){return x.y>y.y;}
};
priority_queue<node> q;
struct edge{int to,next,w;}g[MN];
struct nowf{int sz,ff,ans;}gf[MM],fa[MN];
void ins(int u,int v,int w){g[++num].next=head[u];head[u]=num;g[num].to=v;g[num].w=w;}
void dij(){
	memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));q.push((node){1,dis[1]=0});
	while(!q.empty()){
		node tmp=q.top();q.pop();if(vis[tmp.x])continue;vis[tmp.x]=1;
		for(int i=head[tmp.x];i;i=g[i].next)if((!vis[g[i].to])&&dis[g[i].to]>dis[tmp.x]+g[i].w)q.push((node){g[i].to,dis[g[i].to]=dis[tmp.x]+g[i].w});
	}
}
bool cmp(int xx,int yy){return v[xx]<v[yy];}
int getf(int xx){return fa[xx].ff==xx?xx:getf(fa[xx].ff);};
void upd(int &k,int l,int r,int a,nowf ad){
	ls[++qsum]=ls[k],rs[qsum]=rs[k],k=qsum;if(l==r)return (void)(gf[k]=ad);int mid=(l+r)>>1;
	if(a<=mid)upd(ls[k],l,mid,a,ad);else upd(rs[k],mid+1,r,a,ad);
}
nowf que(int k,int l,int r,int a){
	if(l==r)return gf[k];int mid=(l+r)>>1;
	if(a<=mid)return que(ls[k],l,mid,a);return que(rs[k],mid+1,r,a);
}
int fdans(int xx,int yy){
	if(yy<0)return dis[xx];
	nowf tmp;
	while(1){
		tmp=que(rt[yy],1,n,xx);
		if(tmp.ff==xx)break;
		else xx=tmp.ff;
	}
	return tmp.ans;
}
void build(int l,int r,int &k){
	k=++qsum;if(l==r)return (void)(gf[k]=fa[l]);int mid=(l+r)>>1;
	build(l,mid,ls[k]),build(mid+1,r,rs[k]);
}
int main(){
//	freopen("return5.in","r",stdin);
//	freopen("return.out","w",stdout);
	scanf("%d",&T);int xx,yy;	while(T--){
	//	DWORD st = GetTickCount();
		scanf("%d%d",&n,&m);memset(head,0,sizeof(head));memset(fa,0,sizeof(fa));qsum=num=tt=tot=0;
		for(int i=1;i<=m;i++)scanf("%d%d%d%d",&x[i],&y[i],&len[i],&v[i]),ins(x[i],y[i],len[i]),ins(y[i],x[i],len[i]),nnum[++tt]=v[i],id[i]=i;nnum[++tt]=0x7fffffff;
		sort(nnum+1,nnum+tt+1);tt=unique(nnum+1,nnum+tt+1)-nnum;sort(id+1,id+m+1,cmp);
		dij();//DWORD et=GetTickCount();cout<<"s1:"<<(et-st)<<"ms"<<endl;
		v[0]=-1;for(int i=1;i<=n;i++)fa[i]=(nowf){1,i,dis[i]};build(1,n,rt[0]);//et=GetTickCount();cout<<"s2:"<<(et-st)<<"ms"<<endl;
		for(int i=m;i>=1;i--){
			if(v[id[i]]!=v[id[i+1]])rt[++tot]=rt[tot-1];
			int xx=getf(x[id[i]]),yy=getf(y[id[i]]);
			if(xx==yy)continue;
			if(fa[xx].sz<fa[yy].sz)swap(xx,yy);
			fa[xx]=(nowf){fa[xx].sz+fa[yy].sz,xx,min(fa[xx].ans,fa[yy].ans)},fa[yy].ff=xx;
			upd(rt[tot],1,n,yy,fa[yy]),upd(rt[tot],1,n,xx,fa[xx]);
		}//et=GetTickCount();cout<<"s3:"<<(et-st)<<"ms"<<endl;
		scanf("%d%d%d",&Q,&k,&s);int lstans=0;
		for(int i=1;i<=Q;i++){
			scanf("%d%d",&xx,&yy);
			xx=(xx+1ll*k*lstans-1)%n+1,yy=(yy+k*lstans)%(s+1);
			yy=upper_bound(nnum+1,nnum+tt,yy)-nnum;
			lstans=fdans(xx,tot-yy+1);
			printf("%d\n",lstans);
		}//et=GetTickCount();cout<<"s4:"<<(et-st)<<"ms"<<endl;
	}
}

评测结果