代码

#include <bits/stdc++.h>

typedef int ll;
#define $(...) fprintf(stderr,__VA_ARGS__);
inline ll read() {
	static char c;
	static ll x;
	while (c = getchar(), !isdigit(c));
	x = c - '0';
	while (c = getchar(), isdigit(c))
		x = (x << 1) + (x << 3) + c - '0';
	return x;
}

int n, m, Q, K, S;
struct edge {
	int pre, to, l, a;
} gs[1000000];
int head[200200], gc;
void add(int x, int y, int l, int a) {
	gs[++gc] = (edge) {head[x], y, l, a};
	head[x] = gc;
}

bool vis[200200];
ll dis[200200];
namespace one {
	std::queue<int> q;
	void spfa() {
		while (!q.empty()) q.pop();
		for (int i = 1; i <= n; ++i)
			dis[i] = 0x7f7f7f7f, vis[i] = 0;

		dis[1] = 0;
		q.push(1);
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			for (int i = head[x]; i; i = gs[i].pre) {
				if (dis[gs[i].to] <= dis[x] + gs[i].l) continue;
				dis[gs[i].to] = dis[x] + gs[i].l;
				if (!vis[gs[i].to]) {
					q.push(gs[i].to);
					vis[gs[i].to] = 1;
				}
			}
			vis[x] = 0;
		}
	}

	void solve() {
		spfa();

		assert(K == 0);
		for (int i = 1; i <= Q; ++i) {
			int v = read(), p = read();
			if (p == 0) {
				puts("0");
				continue;
			}
			printf("%d\n", dis[v]);
		}
	}
}

const int N = 10000000;
int root[200200], ids;
int son[2][N], dad[N], rank[N];
ll ans[N];
#define lc(x) son[0][x]
#define rc(x) son[1][x]

namespace sol {
	int build(int l = 1, int r = n) {
		int x = ++ids;
		if (l == r) {
			dad[x] = l;
			ans[x] = dis[l];
			rank[x] = 0;
			return x;
		}
		int mid = (l + r) >> 1;
		lc(x) = build(l, mid);
		rc(x) = build(mid + 1, r);
		return x;
	}

	bool cmp(const edge &a, const edge &b) {
		return a.a < b.a;
	}

	int query(int p, int x, int l = 1, int r = n) {
		if (l == r)
			return x;
		int mid = (l + r) >> 1;
		if (p <= mid) return query(p, lc(x), l, mid);
		return query(p, rc(x), mid + 1, r);
	}

	int modify(int p, int newdad, ll newans, int newrank, int x, int l = 1, int r = n) {
		int ret = ++ids;
		lc(ret) = lc(x);
		rc(ret) = rc(x);
		if (l == r) {
			dad[ret] = newdad;
			ans[ret] = newans;
			rank[ret] = newrank;
			return ret;
		}
		int mid = (l + r) >> 1;
		if (p <= mid) lc(ret) = modify(p, newdad, newans, newrank, lc(x), l, mid);
		else rc(ret) = modify(p, newdad, newans, newrank, rc(x), mid + 1, r);
		// $("%d %d %d %d %d %d %d\n", p, newdad, newans, newrank, x, l, r);
		// $("%d %d %d %d\n", lc(x), rc(x), lc(ret), rc(ret));
		return ret;
	}

	void debug(int x, int l = 1, int r = n) {
		if (l == r) {
			printf("pos %d\tnode %d\tdad %d\tans %d\trank %d\n", l, x, dad[x], ans[x], rank[x]);
			return;
		}
		// printf("node %d\tlc %d\trc %d\n", x, lc(x), rc(x));
		debug(lc(x), l, (l + r) >> 1);
		debug(rc(x), (l + r) / 2 + 1, r);
	}

	int merge(int x, int y, int pre) {
		while (dad[query(x, pre)] != x) x = dad[query(x, pre)];
		while (dad[query(y, pre)] != y) y = dad[query(y, pre)];
		int px = query(x, pre), py = query(y, pre);
		// $("Merging %d %d\n", x, y);
		if (px == py) return pre;
		if (rank[px] > rank[py])std::swap(px, py);
		int ret = modify(y, y, std::min(ans[px], ans[py]), rank[py] + (rank[px] == rank[py]), pre);
		// $("\nOLD\n");
		// debug(pre);
		// $("NEW\n");
		// debug(ret);
		// $("ChangeX %d %d %d %d\n", px, py, dad[py], ans[py]);
		return modify(x, y, ans[px], rank[px], ret);
	}

	std::vector<int> ps;
	void solve() {
		one::spfa();
		ps.clear();
		ps.push_back(0);
		for (int i = 2; i <= gc; i += 2)
			ps.push_back(gs[i].a);
		std::sort(ps.begin(), ps.end());
		ps.resize(std::unique(ps.begin(), ps.end()) - ps.begin());

		ids = 0;
		root[ps.size() - 1] = build();
		std::sort(gs + 2, gs + 1 + gc, cmp);

		for (int i = ps.size() - 2, j = gc; ~i; --i) {
			// $("Constructing %d %d\n", i, ps[i]);
			root[i] = root[i + 1];
			while (j > 0 && gs[j].a > ps[i])
				root[i] = merge(gs[j].to, gs[j ^ 1].to, root[i]), j -= 2;
		}
		ps.push_back(1e9 + 7);
		root[ps.size() - 1] = root[ps.size() - 2];

		// for (int i = 0; i < ps.size(); ++i) {
		// 	$("TREE %d line %d\n", i, ps[i]);
		// 	debug(root[i]);
		// 	$("\n");
		// }

		ll lastans = 0;
		for (int i = 1; i <= Q; ++i) {
			int v = (read() + K * lastans - 1) % n + 1, p = (read() + K * lastans) % (S + 1);
			p = std::upper_bound(ps.begin(), ps.end(), p) - ps.begin() - 1;
			while (dad[query(v, root[p])] != v) v = dad[query(v, root[p])];
			printf("%d\n", lastans = ans[query(v, root[p])]);
		}
	}
}

//Attention: the answer may exceed int
void solve() {
	bool flag = 1;
	n = read(), m = read();
	for (int i = 1; i <= m; ++i) {
		int x = read(), y = read(), l = read(), a = read();
		if (a != 1) flag = 0;
		add(x, y, l, a);
		add(y, x, l, a);
	}
	Q = read(), K = read(), S = read();

	if (flag) {one::solve(); return;}
	sol::solve();
}

void init() {
	gc = 1;
	memset(head, 0, sizeof head);
}
int main() {
	int T = read();
	while (T--) {
		init();
		solve();
	}
}

评测结果