代码

#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=200005;
int n,m,Q,K,S,dis[MAXN];
struct node{int to,dis,h;};
vector <node> a[MAXN];
bool only_tag,chain_tag;
void read(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) a[i].clear();
	memset(dis,63,sizeof(dis));
	int u,v,w,h;
	only_tag=chain_tag=true;
	for (int i=1;i<=m;i++){
		scanf("%d%d%d%d",&u,&v,&w,&h);
		if (h!=1) only_tag=false;
		if (u+1!=v) chain_tag=false;
		a[u].push_back((node){v,w,h});
		a[v].push_back((node){u,w,h});
	}
	scanf("%d%d%d",&Q,&K,&S);
}
queue <int> q;
void spfa(){
	q.push(1); dis[1]=0;
	while (!q.empty()){
		int o=q.front(); q.pop();
		for (int i=0;i<a[o].size();i++){
			int v=a[o][i].to,d=a[o][i].dis;
			if (dis[v]>dis[o]+d) dis[v]=dis[o]+d,q.push(v);
		}
	}
}
void solve(){
	int p,v,lastans=0;
	for (int i=1;i<=Q;i++){
		scanf("%d%d",&p,&v);
		if (only_tag) {
			if (v>=1) printf("%d\n",dis[p]);
			else puts("0");
		}
		else if (chain_tag){
			p=(p+lastans*K-1)%n+1;
			v=(v+lastans*K)%(S+1);
			lastans=0;
			while (p!=1){
				int choice=a[p][0].to!=p-1;
				if (a[p][choice].h<=v) {
					lastans+=dis[p];
					break;
				}
				p--;
			}
			printf("%d\n",lastans);
		}
	}
}
int T;
int main(){
	scanf("%d",&T);
	while (T--){
		read();
		spfa();
		solve();
	}
	return 0;
}

评测结果