代码

//sro zbw ak noi2018 orz
#include<bits/stdc++.h>
using namespace std;
#define FE "return"
#define pb push_back
#define clr(a) memset(a,0,sizeof(a))
const int N=500005,N2=N<<1,inf=0x3f3f3f3f;
int n,m,d[N2],mn[N2],vis[N],t,fa[N2][20],uf[N2],lust,Q,k,s;
struct node{int d,n;};
bool operator<(node a,node b){return b.d<a.d;}
priority_queue<node>q;
vector<int>e[N],f[N];
void dbg(string a,node x){cerr<<a<<"  ("<<x.d<<","<<x.n<<")\n";}
struct edge{int u,v,w,x;}ed[N2];
bool cmp(edge a,edge b){return b.x<a.x;}
void init();
int find(int a){if(uf[a])return uf[a]=find(uf[a]);return a;}
void build(){clr(fa),clr(uf),clr(mn);
	for(int i=1;i<=n;i++)mn[i]=inf;
	for(int i=0,j=n;i<m;i++){
		int v=find(ed[i].v),u=find(ed[i].u);
		if(v==u)continue;
		uf[v]=uf[u]=++j,fa[v][0]=fa[u][0]=j,d[j]=inf,mn[j]=ed[i].x;
	}n=(n<<1)-1;
	for(int i=1;i<=n;i++)
		d[fa[i][0]]=min(d[fa[i][0]],d[i]),mn[fa[i][0]]=min(mn[fa[i][0]],mn[i]);
	for(int k=1;k<20;k++)for(int i=1;i<=n;i++)fa[i][k]=fa[fa[i][k-1]][k-1];
	//for(int i=1;i<=n;i++)printf("%d %d %d\n",d[i],mn[i],fa[i][0]);
}
void solve(){lust=0;
	scanf("%d%d%d",&Q,&k,&s);
	while(Q--){
		int a,b;scanf("%d%d",&a,&b);
		a=(a+(long long)k*lust-1)%((n+1)>>1)+1,b=(b+(long long)k*lust)%(s+1);//printf("query %d %d\n",a,b);
		for(int k=19;~k;k--)if(b<mn[fa[a][k]])a=fa[a][k];
		printf("%d\n",lust=d[a]);
	}
}
int main(){
	freopen(FE".in","r",stdin);
	freopen(FE".out","w",stdout);
	scanf("%d",&t);while(t--){
		init();
		build();
		solve();
	}return 0;
}
void init(){clr(vis),clr(d);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)e[i].clear(),f[i].clear();
	for(int i=0;i<m;i++){
		int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
		e[a].pb(b),f[a].pb(c);
		e[b].pb(a),f[b].pb(c);
		ed[i]=(edge){a,b,c,d};
	}sort(ed,ed+m,cmp);
	for(int i=2;i<=n;i++)d[i]=inf;
	q.push((node){0,1});
	while(!q.empty()){
		node nod=q.top();q.pop();//dbg("out",nod);
		int v=nod.n;
		if(vis[v])continue;vis[v]=1;//dbg("ok",nod);
		for(int i=0;i<(int)e[v].size();i++){
			int u=e[v][i],w=d[v]+f[v][i];//dbg("chk",(node){w,u});
			if(!vis[u]&&w<d[u])d[u]=w,q.push((node){w,u});//dbg("in",(node){w,u});
		}
	}//for(int i=1;i<=n;i++){if(d[i]==inf)d[i]=2147483647;printf("%d ",d[i]);}
} 

评测结果