代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define cl(x,y) memset(x,y,sizeof(x))
using namespace std;
inline char nc(){
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
inline int red(){
	int res=0,f=1;char ch=nc();
	while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=nc();}
	while ('0'<=ch&&ch<='9') res=res*10+ch-48,ch=nc();
	return res*f;
}

const int maxn=200005,maxe=800005,maxq=400005;
int tst,n,e,q,K,S,fa[maxn],s[maxn],ans[maxq];
inline int getfa(int x) {return fa[x]==x?x:fa[x]=getfa(fa[x]);}
inline void merge(int x,int y){
	int fx=getfa(x),fy=getfa(y);
	if (fx!=fy) s[fy]=min(s[fy],s[fx]),fa[fx]=fy;
}
struct edge{
	int x,y,w,h;
	bool operator<(const edge&b)const {return h>b.h;}
}a[maxe];
struct data{
	int h,x,id;
	bool operator<(const data&b)const {return h>b.h;}
}Q[maxq];
int tot,son[maxe],nxt[maxe],lnk[maxn],w[maxe];
inline void add(int x,int y,int z){
	son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;w[tot]=z;
}
int que[maxn],dst[maxn];bool vis[maxn];
void spfa(){
//	cl(dst,0x7f);cl(vis,0);
	for (int i=1;i<=n;i++) dst[i]=0x7f7f7f7f,vis[i]=0;
	int hed=0,til=1;
	que[1]=1;dst[1]=0;
	while (hed!=til){
		int x=que[hed=(hed+1)%maxn];
		vis[x]=0;
		for (int j=lnk[x];j;j=nxt[j])
		 if (dst[son[j]]>dst[x]+w[j]){
		 	dst[son[j]]=dst[x]+w[j];
		 	if (!vis[son[j]]){
		 		que[til=(til+1)%maxn]=son[j],vis[son[j]]=1;
		 		if (dst[que[hed]]>dst[que[til]]) swap(que[hed],que[til]);
			}
		 }
	}
}
int main(){
	tst=red();
	while (tst--){
		n=red(),e=red();
		for (int i=1;i<=n;i++) lnk[0]=0;tot=0;
		for (int i=1;i<=e;i++)
		 a[i].x=red(),a[i].y=red(),a[i].w=red(),a[i].h=red(),
		 add(a[i].x,a[i].y,a[i].w),add(a[i].y,a[i].x,a[i].w);
		q=red(),K=red(),S=red();
		if (K==0){
			for (int i=1;i<=q;i++) Q[i].x=red(),Q[i].h=red(),Q[i].id=i;
			sort(a+1,a+1+e); sort(Q+1,Q+1+q); spfa();
			for (int i=1;i<=n;i++) fa[i]=i,s[i]=dst[i];
			for (int i=1,j=1;i<=q;i++){
				while (j<=e&&a[j].h>Q[i].h) merge(a[j].x,a[j].y),j++;
				ans[Q[i].id]=s[getfa(Q[i].x)];
			}
			for (int i=1;i<=q;i++) printf("%d\n",ans[i]);
		}else{
			sort(a+1,a+1+e);spfa();
			int lastans=0;
			for (int i=1;i<=q;i++){
				int x=(red()+K*lastans-1)%n+1,h=(red()+K*lastans)%(S+1);
				for (int j=1;j<=n;j++) fa[j]=j,s[j]=dst[j];
				for (int j=1;j<=e&&a[j].h>h;j++) merge(a[j].x,a[j].y);
				printf("%d\n",lastans=s[getfa(x)]);
			}
		}
	}
	//检查清数组 
	return 0;
}

评测结果