代码

#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<queue>
#define N 200005
using namespace std;

struct Edge{
	int v,nxt,l,h;
}e[N<<1];
int head[N],tot;

void AddEdge(int u,int v,int l,int h){
	e[++tot]=(Edge){v,head[u],l,h};head[u]=tot;
	e[++tot]=(Edge){u,head[v],l,h};head[v]=tot;
}

int vis[N];
void dfs(int x,int limit){
	vis[x]=true;
	for(int i=head[x];i;i=e[i].nxt){
		if(e[i].h<=limit)continue;
		if(!vis[e[i].v])dfs(e[i].v,limit);
	}
}
int v[N];
int dis[N];
void spfa(){
	int top;
	memset(v,0,sizeof(v));
	memset(dis,10,sizeof(dis));
	dis[1]=0;v[1]=1;
	queue<int>que;
	que.push(1);
	while(!que.empty()){
		top=que.front();que.pop(),v[top]=false;
		for(int i=head[top];i;i=e[i].nxt){
			if(dis[e[i].v]>dis[top]+e[i].l){
				dis[e[i].v]=dis[top]+e[i].l;
				if(!v[e[i].v])
					v[e[i].v]=1,que.push(e[i].v);
			}
		}
	}
}

int main(){
	int T,n,m,q,s,lastans,a,b,c,d,K;
	scanf("%d",&T);
	while(T--){
		memset(head,0,sizeof(head));tot=0;
		lastans=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;++i){
			scanf("%d%d%d%d",&a,&b,&c,&d);
			if(a!=b)AddEdge(a,b,c,d);
		}
		scanf("%d%d%d",&q,&K,&s);
		spfa();
		while(q--){
			int ans=0x3f3f3f3f;
			scanf("%d%d",&a,&b);
			a=(a+K*lastans-1)%n+1;
			b=(b+K*lastans)%(s+1);
			memset(vis,false,sizeof(vis));
			dfs(a,b);
			for(int i=1;i<=n;++i)
				if(vis[i])
					ans=min(ans,dis[i]);
			printf("%d\n",ans);
			lastans=ans;
		}
	}
	return 0;
}

评测结果