代码

#include<set>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define fi first
#define se second
using namespace std;

const int N = 8e5 + 5;

int n, m, T;

struct edge {
	int final[N], next[N], to[N], l[N], a[N], tot;
	void link(int x, int y, int z, int u) {
		next[++ tot] = final[x], to[tot] = y, l[tot] = z, a[tot] = u, final[x] = tot;
		next[++ tot] = final[y], to[tot] = x, l[tot] = z, a[tot] = u, final[y] = tot;
	}
	void cl() {
		fo(i, 1, n) final[i] = 0;
		fo(i, 1, tot) next[i] = 0;
		tot = 0;
	}
} e;

struct node {
	int u, v, l, a;
} b[N];

int dis[N], bz[N];

#define P pair<int, int>
multiset<P> s;

void spfa() {
	s.clear();
	memset(bz, 0, sizeof bz);
	fo(i, 1, n) dis[i] = 2e9; dis[1] = 0;
	fo(i, 1, n) s.insert(mp(dis[i], i));
	fo(i, 1, n) {
		P w = *s.begin(); int x = w.se;
		bz[x] = 1; s.erase(s.find(w));
		for(int j = e.final[x]; j; j = e.next[j]) {
			int y = e.to[j];
			if(!bz[y] && dis[x] + e.l[j] < dis[y]) {
				s.erase(s.find(mp(dis[y], y)));
				dis[y] = dis[x] + e.l[j];
				s.insert(mp(dis[y], y));
			}
		}
	}
}

int Q, K, S, x, y, ans;

int cmp(node a, node b) {
	return a.a > b.a;
}

int num[N], tn, a[N];

struct tree {
	int l, r, f, mi;
} t[N * 30];
int tot, pl, pr, pf, pm;

void add(int &i, int x, int y) {
	if(y < pl || x > pr) return;
	t[++ tot] = t[i]; i = tot;
	if(x == y) {t[i].f = pf; t[i].mi = pm; return;}
	int m = x + y >> 1;
	add(t[i].l, x, m); add(t[i].r, m + 1, y);
}

void fi(int &i, int x, int y) {
	if(y < pl || x > pr) return;
	if(x == y) {pf = t[i].f; pm = t[i].mi; return;}
	int m = x + y >> 1;
	fi(t[i].l, x, m); fi(t[i].r, m + 1, y);
}

int f[N], mi[N], g[N], z[N];

int find(int x) {
	if(x == f[x]) return x;
	int fa = find(f[x]);
	pl = pr = x; pf = fa; pm = mi[x];
	add(g[tn], 1, n);
	return f[x] = fa;
}

void bin(int x, int y) {
	if(find(x) != find(y)) {
		if(z[f[x]] > z[f[y]]) swap(x, y);
		
		pl = pr = f[x]; pf = f[y]; pm = mi[f[x]];
		add(g[tn], 1, n);
		
		z[f[y]] += z[f[x]];
		mi[f[y]] = min(mi[f[y]], mi[f[x]]);
		f[f[x]] = f[y];
		
		pl = pr = f[y]; pf = f[y]; pm = mi[f[y]];
		add(g[tn], 1, n);
	}
}

void read(int &x) {
	char ch = ' ';
	for(; ch < '0' || ch > '9';) ch = getchar();
	x = 0; for(; ch >= '0' && ch <= '9'; ch=getchar()) x = x * 10 + ch - 48;
}

void write(int x) {
	int d[10]; d[0] = 0;
	if(x == 0) {
		putchar('0');
	} else {
		while(x) d[++ d[0]] = x % 10, x /= 10;
		for(; d[0]; d[0] --) putchar(d[d[0]] + '0');
	}
}

int main() {
	freopen("return.in", "r", stdin);
	freopen("return.out", "w", stdout);
	for(scanf("%d", &T); T; T --) {
		e.cl();
		scanf("%d %d", &n, &m);
		fo(i, 1, m) {
			read(b[i].u);
			read(b[i].v);
			read(b[i].l);
			read(b[i].a);
			e.link(b[i].u, b[i].v, b[i].l, b[i].a);
		}
		scanf("%d %d %d", &Q, &K, &S);
		spfa();
		fo(i, 1, tot) t[i].l = t[i].r = 0;
		tot = 0; fo(i, 0, m) g[i] = 0;
		g[0] = ++ tot;
		fo(i, 1, n) {
			f[i] = i; mi[i] = dis[i]; z[i] = 1;
			pf = i; pm = dis[i]; pl = pr = i;
			add(g[0], 1, n);
		}
		sort(b + 1, b + m + 1, cmp);
		tn = 0; int la = 1;
		fo(i, 2, m + 1) { 
			if(i > m || b[i].a != b[i - 1].a) {
				t[++ tot] = t[g[tn]]; g[++ tn] = tot;
				a[tn] = b[i - 1].a;
				fo(j, la, i - 1) bin(b[j].u, b[j].v);
				fo(j, la, i - 1) find(b[j].u), find(b[j].v);
				la = i;
			}
		}
		ans = 0;
		fo(ii, 1, Q) {
			scanf("%d %d", &x, &y);
			x = (x + K * ans - 1) % n + 1;
			y = (y + K * ans) % (S + 1);
			int as = 0;
			for(int l = 1, r = tn; l <= r; ) {
				int m = l + r >> 1;
				if(a[m] > y) as = m, l = m + 1; else r = m - 1;
			}
			pf = x;
			do {
				x = pf; pl = pr = x;
				fi(g[as], 1, n);
			} while(pf != x);
			pl = pr = pf;
			fi(g[as], 1, n);
			ans = pm;
			write(ans); putchar('\n');
		}
	}
}

评测结果