代码

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>

const int N = 200005, M = 400005, INF = 2e9 + 7;

int tc, n, m, s, Qi;
int dis[N], flg[N], ans[M];
std::priority_queue<std::pair<int, int> > Q;

inline void Read(int &x) {
	x = 0; static char c;
	for (c = getchar(); c < '0' || c > '9'; c = getchar());
	for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
}

struct Que {
	int u, v, a, l, ty, id;
	inline friend bool operator < (Que a, Que b) {
		return (a.a == b.a)? (a.ty < b.ty) : (a.a > b.a);
	}
} q[M << 1];

namespace DSU {
	int fa[N], mdi[N];
	void Init() {
		for (int i = 1; i <= n; ++i) {
			fa[i] = i; mdi[i] = dis[i];
		}
	}
	int Seek(int x) {
		return (x == fa[x])? (x) : (fa[x] = Seek(fa[x]));
	}
	inline void Merge(int x, int y) {
		x = Seek(x); y = Seek(y);
		fa[y] = x; mdi[x] = std::min(mdi[x], mdi[y]);
	}
	inline int Query(int x) {
		return mdi[Seek(x)];
	}
}

int yun, las[N], to[M << 1], pre[M << 1], wi[M << 1];
inline void Add(int a, int b, int c) {
	to[++yun] = b; wi[yun] = c; pre[yun] = las[a]; las[a] = yun;
}

void Dij() {
	for (int i = 1; i <= n; ++i) {
		dis[i] = INF; flg[i] = 0;
	}
	dis[1] = 0;
	Q.push(std::make_pair(0, 1));
	for (; !Q.empty(); ) {
		int x = Q.top().second; Q.pop();
		if (flg[x]) continue;
		flg[x] = 1;
		for (int i = las[x]; i; i = pre[i]) {
			if (dis[to[i]] > dis[x] + wi[i]) {
				dis[to[i]] = dis[x] + wi[i];
				Q.push(std::make_pair(-dis[to[i]], to[i]));
			}
		}
	}
}

int main() {
	scanf("%d", &tc);
	for (int fk; tc; --tc) {
		memset(las, 0, sizeof las);
		yun = 0;
		scanf("%d%d", &n, &m);
		for (int i = 1, x, y, a, l; i <= m; ++i) {
			//scanf("%d%d%d%d", &x, &y, &l, &a);
			Read(x); Read(y); Read(l); Read(a);
			Add(x, y, l); Add(y, x, l);
			q[i] = (Que) { x, y, a, l, 1, 0 };
		}
		scanf("%d%d%d", &Qi, &fk, &s);
		for (int i = 1, v, a; i <= Qi; ++i) {
			//scanf("%d%d", &v, &a);
			Read(v); Read(a); a %= s + 1;
			q[i + m] = (Que) { v, 0, a, 0, 0, i };
		}
		std::sort(q + 1, q + 1 + m + Qi);
		Dij(); DSU::Init();
		
		for (int i = 1; i <= m + Qi; ++i) {
			if (q[i].ty == 0) {
				ans[q[i].id] = DSU::Query(q[i].u);
			} else {
				DSU::Merge(q[i].u, q[i].v);
			}
		}
		for (int i = 1; i <= Qi; ++i) {
			printf("%d\n", ans[i]);
		}
	}
	
	return 0;
}

评测结果