代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cctype>
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 400010;
const int M = 800010;
const int Iinf = 1e9;
const LL Linf = 1e18;

struct Edge{
	int to,nxt,w,h;
	Edge() {}
	Edge(int a,int b,int c,int d) {to = a,w = b,h = c,nxt =d;}
}e[M];
int head[N],q[N],val[N],Height[N],fa[N];
int n,m,L,R,Enum,Q,K,S;
bool vis[N];
LL dis[N];


void add_edge(int u,int v,int w,int h) {
	++Enum; e[Enum] = Edge(v,w,h,head[u]); head[u] = Enum;
	++Enum; e[Enum] = Edge(u,w,h,head[v]); head[v] = Enum;
}

void init() {
	n = m = L = R = Enum = Q = K = S = 0;
	memset(head,0,sizeof(head));
	memset(val,0,sizeof(val));
	memset(Height,0,sizeof(Height));
}
void getuh(int &u,int &h,LL last) {
	u = (u + K * last - 1) % n + 1;
	h = (h + K * last) % (S + 1);
}

void dfs(int u) {
	for (int i=head[u]; i; i=e[i].nxt) {
		int v = e[i].to;
		if (v == fa[u]) continue;
		fa[v] = u;val[v] = e[i].w;Height[v] = e[i].h;
		dfs(v);
	}
}

void solve2() { // 树
	dfs(1); 
	LL last = 0;
	while (Q--) {
		int u = read(),h = read();
		getuh(u,h,last);
		int flag = 0;
		LL ans = 0;
		for (int i=u; i!=1; i=fa[i]) {
			if (Height[i] <= h) flag = 1;
			if (flag) ans += val[i];
		}
		printf("%lld\n",ans);
		last = ans;
	}
}

LL bfs(int u,int h) {
	LL Ans = Linf;
	for (int i=1; i<=n; ++i) vis[i] = 0;
	L = 1,R = 0;
	q[++R] = u;
	vis[u] = 1;
	while (L <= R) {
		int u = q[L++];
		Ans = min(Ans,dis[u]);
		for (int i=head[u]; i; i=e[i].nxt) {
			int v = e[i].to;
			if (vis[v] == 0 && e[i].h > h) {
				vis[v] = 1;
				q[++R] = v;
			}
		}
	}
	return Ans;
}

void spfa() {
	for (int i=1; i<=n; ++i) vis[i] = false,dis[i] = Linf;
	L = 1,R = 0;
	q[++R] = 1;
	vis[1] = true;
	dis[1] = 0;
	while (L <= R) {
		int u = q[L++];
		for (int i=head[u]; i; i=e[i].nxt) {
			int v = e[i].to;
			if (dis[v] > dis[u] + e[i].w) {
				dis[v] = dis[u] + e[i].w;
				if (!vis[v]) {
					q[++R] = v;
					vis[v] = true;
				}
			}
		}
		vis[u] = false;
	}
}

void solve3() { // bfs 
	spfa();
	LL last = 0;
	while (Q--) {
		int u = read(),h = read();
		getuh(u,h,last);
		last = bfs(u,h);
		printf("%lld\n",last);
	}
}

void solve4() { // a = 1
	for (int i=1; i<=n; ++i) vis[i] = false,dis[i] = Linf;
	L = 1,R = 0;
	q[++R] = 1;
	vis[1] = true;
	dis[1] = 0;
	while (L <= R) {
		int u = q[L++];
		for (int i=head[u]; i; i=e[i].nxt) {
			int v = e[i].to;
			if (dis[v] > dis[u] + e[i].w) {
				dis[v] = dis[u] + e[i].w;
				if (!vis[v]) {
					q[++R] = v;
					vis[v] = true;
				}
			}
		}
		vis[u] = false;
	}	
	while (Q--) {
		int u = read(),H = read();
		if (H >= 1) {
			printf("%lld\n",dis[u]);
		}
		else {
			printf("0\n");
		}		
	}
}

void solve5() { // 链 
	LL last = 0,ans = 0;
	int flag = 0;
	while (Q--) {
		int u = read(),h = read();
	//	getuh(u,h,last);
		ans = 0,flag = 0;
		for (int i=u; i>=2; --i) {
			if (Height[i] <= h) flag = 1;
			if (flag) ans += val[i];
		}
		printf("%lld\n",ans);
		last = ans;
	}
}

void solve1() {
	init();
	n = read(),m = read();
	bool f1 = true,f2 = true;
	for (int i=1; i<=m; ++i) {
		int u = read(),v = read(),l = read(),a = read();
		add_edge(u,v,l,a);
		if (a != 1) f1 = false;
		if (u + 1 != v) f2 = false;
		val[v] = l;Height[v] = a;
	}
	Q = read(),K = read(),S = read();
	
	if (f1) {solve4(); return ;}
	if (f2) {solve5(); return ;}
	if (n == m + 1) {solve2(); return ;}
	solve3();
}

int main() {
	


	int Case = read();
	while (Case--) solve1();
	return 0;
}

评测结果