代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;
const int N = 4e5 + 10;

int highsmile;
int n, m, q, k, s;

#define gc getchar()

inline int read() {
	int x = 0, f = 1; char c = gc;
	while(c < '0' || c > '9') {if(c == '-') f = -1;c = gc;}
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
	return x * f;
}

int head[N], now = 1;
struct Node {
	int u, v, w, high, nxt;
} G[N];

void Add(int u, int v, int w, int high) {
	G[now].high = high; G[now].v = v; G[now].w = w; G[now].nxt = head[u]; head[u] = now ++;
}

#define LL long long

LL dis[N];
std:: queue <int> Q;
bool vis[N];

void Spfa(int start) {
	for(int i = 1; i <= n; i ++) dis[i] = 1e18;
	dis[start] = 0;
	Q.push(start);
	while(!Q.empty()) {
		int topp = Q.front();
		Q.pop();
		vis[topp] = 0;
		for(int i = head[topp]; ~ i; i = G[i].nxt) {
			int v = G[i].v;
			if(dis[v] > dis[topp] + G[i].w) {
				dis[v] = dis[topp] + G[i].w;
				if(!vis[v]) {
					vis[v] = 1;
					Q.push(v);
				}
			}
		}
	}
}

void Work_1() {
	for(int i = 1; i <= n; i ++) head[i] = -1;
	for(int i = 1; i <= m; i ++) {
		int u = read(), v = read(), w = read();
		highsmile = read();
		Add(u, v, w, 1), Add(v, u, w, 1);
	}
	q = read(), k = read(), s = read();
	if(!q) return ;
	Spfa(1);
	for(; q; q --) {
		int v = read(), p = read();
		if(p < highsmile) {
			puts("0");
		} else {
			printf("%lld\n", dis[v]);
		}
	}
}

LL high[N], sum[N], w[N];

void Work_2() {
	for(int i = 1; i <= n; i ++) head[i] = -1;
	for(int i = 1; i <= m; i ++) {
		int u = read(), v = read(), w_ = read(), high_ = read();
		w[v] = w_; high[v] = high_;
	}
	for(int i = 2; i <= n; i ++) sum[i] = sum[i - 1] + w[i];
	q = read(), k = read(), s = read();
	LL lastans = 0;
	for(; q; q --) {
		int v = read(), p = read();
		v = (v + k * lastans - 1) % n + 1;
		p = (p + k * lastans) % (s + 1);
		int now_1 = v;
		while(high[now_1] > p && now_1 != 1) {
			now_1 --;
		}
		if(now_1 == 1) {
			lastans = 0;
			puts("0");
		}
		else {
			lastans = sum[now_1];
			//std:: cout << sum[now_1] << "\n";	
			printf("%lld\n", lastans);
		}
	}
}

int h[N][30], who[N][30];
LL f[N][30];
int deep[N];

void Dfs_1(int u, int f_, int dep) {
	deep[u] = dep;
	for(int i = head[u]; ~ i; i = G[i].nxt) {
		int v = G[i].v;
		if(v == f_) continue;
		h[v][0] = G[i].high;
		f[v][0] = G[i].w;
		who[v][0] = u;
		Dfs_1(v, u, dep + 1);
	}
}

void Before() {
	for(int i = 1; i <= 25; i ++)
		for(int j = 1; j <= n; j ++)
			who[j][i] = who[who[j][i - 1]][i - 1],
			f[j][i] = f[j][i - 1] + f[f[j][i - 1]][i - 1],
			h[j][i] = std:: max(h[j][i - 1], h[who[j][i - 1]][i - 1]);
}

bool See(int x) {
	
}

int Solve(int v, int p) {
	int l = 0, r = deep[v] - deep[1] + 1;
	int ans_solve;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(See(mid)) {
			
		}ans_solve = mid, r = mid - 1;
	//	else l = mid + 1;
	}
	
}

void Work_3() {
	for(int i = 1; i <= n; i ++) head[i] = -1;
	for(int i = 1; i <= m; i ++) {
		int u = read(), v = read(), w_ = read(), high_ = read();
		Add(u, v, w_, high_), Add(v, u, w_, high_);
	}
	Dfs_1(1, 0, 1);
	Before();
	q = read(), k = read(), s = read();
	LL lastans = 0;
	for(; q; q --) {
		int v = read(), p = read();
		v = (v + k * lastans - 1) % n + 1;
		p = (p + k * lastans) % (s + 1);
		std:: cout << Solve(v, p) << "\n";
	}
}

int main() {
	int t = read();
	for(; t; t --) {
		n = read(), m = read();
		if(n <= 1500 && (m != n - 1)) {
			Work_1();
		} else if(n <= 1500 && m == n - 1) { // Chain
			Work_2();
		} else {
			Work_1(); 
		}
	}
	return 0;
}
/*
1
6 5
1 2 1 2
2 3 2 2
3 4 3 4
4 5 4 3
5 6 5 2
6 0 12
5 5

*/

评测结果