代码

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 200000, maxm = 400000, inf = 2.1e9;
const int maxc = 10000000;
int t, n, m, q, k, s, lst;

struct edge {
	int l, r, w;
	bool operator < (const edge &t) const {
		return w > t.w;
	}
}a[maxm + 10];
struct edge2 {
	int to, len;
};
vector<edge2> g[maxn + 10];
int dis[maxn + 10];
struct hnd {
	int id, v;
	bool operator < (const hnd &t) const {
		return v > t.v;
	}
};
priority_queue<hnd> hp;

void dij() {
	for (int i = 1; i <= maxn; ++i) dis[i] = i == 1 ? 0 : inf;
	hp.push((hnd){1, 0});
	while (!hp.empty()) {
		hnd p = hp.top(); hp.pop();
		if (p.v > dis[p.id]) continue;
		for (int i = 0; i < g[p.id].size(); ++i) {
			edge2 e = g[p.id][i];
			if (p.v + e.len < dis[e.to]) {
				dis[e.to] = p.v + e.len;
				hp.push((hnd){e.to, dis[e.to]});
			}
		}
	}
}

int rt[maxm + 10], lc[maxc + 10], rc[maxc + 10], fa[maxc + 10], val[maxc + 10], ndcnt;

void build(int &p, int ls, int rs) {
	p = ++ndcnt;
	if (ls == rs) {
		fa[p] = -1; val[p] = dis[ls];
	} else {
		int mid = ls + rs >> 1;
		build(lc[p], ls, mid); build(rc[p], mid + 1, rs);
	}
}

void change(int &p, int cmp, int k, int vfa, int vval, int ls, int rs) {
	p = ++ndcnt; lc[p] = lc[cmp]; rc[p] = rc[cmp];
	if (ls == rs) {
		fa[p] = vfa; val[p] = vval;
	} else {
		int mid = ls + rs >> 1;
		if (k <= mid) change(lc[p], lc[cmp], k, vfa, vval, ls, mid);
		else change(rc[p], rc[cmp], k, vfa, vval, mid + 1, rs);
	}
}

int query(int p, int k, int ls, int rs) {
	if (ls == rs) return p;
	else {
		int mid = ls + rs >> 1;
		if (k <= mid) return query(lc[p], k, ls, mid);
		else return query(rc[p], k, mid + 1, rs);
	}
}

pair<int, int> getf(int r, int p) {
	int f = query(r, p, 1, n);
	while (fa[f] > 0) {
		p = fa[f]; f = query(r, p, 1, n);
	}
	return make_pair(p, f);
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; ++i) g[i].clear();
		for (int i = 1; i <= ndcnt; ++i)
			lc[i] = rc[i] = fa[i] = val[i] = 0;
		ndcnt = lst = 0;
		for (int i = 1; i <= m; ++i) {
			int u, v, l, h;
			scanf("%d%d%d%d", &u, &v, &l, &h);
			a[i] = (edge){u, v, h};
			g[u].push_back((edge2){v, l});
			g[v].push_back((edge2){u, l});
		}
		dij(); sort(a + 1, a + m + 1);
		build(rt[0], 1, n);
		for (int i = 1; i <= m; ++i) {
			rt[i] = rt[i - 1];
			pair<int, int> p1 = getf(rt[i], a[i].l), p2 = getf(rt[i], a[i].r);
			if (p1.first != p2.first) {
				if (fa[p1.second] < fa[p2.second]) swap(p1, p2);
				change(rt[i], rt[i], p2.first, fa[p1.second] + fa[p2.second], min(val[p1.second], val[p2.second]), 1, n);
				change(rt[i], rt[i], p1.first, p2.first, 0, 1, n);
			}
		}
		scanf("%d%d%d", &q, &k, &s);
		while (q--) {
			int st, p; scanf("%d%d", &st, &p);
			st = (st + k * lst - 1) % n + 1;
			p = (p + k * lst) % (s + 1);
			int l = 0, r = m;
			while (l != r) {
				int mid = l + r + 1 >> 1;
				if (a[mid].w > p) l = mid;
				else r = mid - 1;
			}
			printf("%d\n", lst = val[getf(rt[l], st).second]);
		}
	}
}

评测结果