代码

#include<bits/stdc++.h>
#define fir first
#define sec second
#define mp make_pair
#define mem(a, b) memset(a, b, sizeof(a))
#define For(i, j, k) for(int i = j; i <= k; ++i)
#define Travel(i, u) for(int i = beg[u], v = to[i]; i; i = nex[i], v = to[i])
using namespace std;

inline int read() {
	int x = 0, p = 1; char c = getchar();
	while(!isdigit(c)) { if(c == '-') p = -1; c = getchar(); }
	while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	return x *= p;
}

inline void File() {
	freopen("return.in", "r", stdin);
	freopen("return.out", "w", stdout);
}

typedef pair<int, int> PII;
const int N = 2e5 + 10, M = N << 2, inf = 2e9;
int n, m, q, k, s, fa[N], vis[N];
int e = 1, beg[N], nex[M], to[M], w[M];
struct edge { int u, v, l, a; }E[M];
struct node { int id, v, p; }Q[M];
int dis[N], ans[M], lstans;

inline bool cmp(const edge &a, const edge &b) { return a.a > b.a; }
inline bool cmpp(const node &a, const node &b) { return a.p > b.p; }
template<typename T> inline bool chkmin(T &a, T b) { return a > b ? a = b, 1 : 0; }

inline int find(int x) {
	if(x == fa[x]) return fa[x];
	int F = fa[x];
	fa[x] = find(fa[x]);
	chkmin(dis[x], dis[F]);
	return fa[x];
}

inline int getfa(int x) {
	if(x == fa[x]) return fa[x];
	return fa[x] = getfa(fa[x]);
}

inline void add(int x, int y, int z) {
	to[++e] = y, nex[e] = beg[x], beg[x] = e, w[e] = z;
	to[++e] = x, nex[e] = beg[y], beg[y] = e, w[e] = z;
}

inline void dijkstra() {
	priority_queue<PII, vector<PII>, greater<PII> > Q;
	For(i, 1, n) vis[i] = 0, dis[i] = inf;
	dis[1] = 0, Q.push(mp(0, 1));
	while(!Q.empty()) {
		PII x = Q.top(); Q.pop();
		int u = x.sec;
		if(!vis[u]) {
			vis[u] = 1;
			Travel(i, u) if(dis[v] >= x.fir + w[i]) {
				dis[v] = x.fir + w[i];
				Q.push(mp(dis[v], v));
			}
		}
	}
}

inline void BF_Solve() {
	For(i, 1, q) {
		int v = read(), p = read();
		lstans = 0; 
		v = (k * lstans + v - 1) % n + 1;
		p = (k * lstans + p) % (s + 1);
		For(i, 1, n) fa[i] = i;
		int now = 1;
		while(E[now].a > p) {
			int u = E[now].u, v = E[now].v, fx = getfa(u), fy = getfa(v);
			if(fx != fy) fa[fx] = fy;
			++ now;
		}
		lstans = inf;
		For(i, 1, n) if(getfa(i) == getfa(v)) chkmin(lstans, dis[i]);
		printf("%d\n", lstans);
	}
}

int main() {
	int Case = read();
	while(Case --) {
		e = 1, mem(beg, 0);
		n = read(), m = read();		
		For(i, 1, m) {
			E[i].u = read(), E[i].v = read(), E[i].l = read(), E[i].a = read();
			add(E[i].u, E[i].v, E[i].l);
		}
		dijkstra(), sort(E + 1, E + 1 + m, cmp);	
		q = read(), k = read(), s = read();	
		if(k == 1) { BF_Solve(); continue; }

		For(i, 1, q) { 
			int v = read(), p = read();
			Q[i] = (node) {i, v, p};
		}

		sort(Q + 1, Q + 1 + q, cmpp);
		For(i, 1, n) fa[i] = i; int now = 1;
		For(i, 1, q) {
			while(E[now].a > Q[i].p && now <= m) {
				int u = E[now].u, v = E[now].v, fx = find(u), fy = find(v);
				if(fx != fy) {
					fa[fx] = fy;
					chkmin(dis[fy], min(dis[fx], dis[fy]));	
				}
				++ now;
			}			
			ans[Q[i].id] = dis[find(Q[i].v)];
		}
		For(i, 1, q) printf("%d\n", ans[i]);
	}
	return 0;
}

评测结果