题解 【P4768 [NOI2018] 归程】

spfa墓前考古并留名。

谨为我们可爱的spfa，上香，烧纸。

---

？这啥题，每次跑一遍最短路？

在这之前需要学习一个叫 kruskal 重构树的东东据说很冷门qaq

什么是 kruskal 重构树呢，回忆一下 kruskal 算法的过程，每当选出一条边，我们是直接将这两个点所在的并查集合并。但在 kruskal 重构树中，是新建一个节点，将这两个端点分别作为这个节点的儿子。

但是并查集有路径压缩，不能维护树的形态，所以我们还要另外存一下这棵树，然后将这条边的边权作为这个新点的点权。由于我们是求的最小生成树，所以整颗重构树是一个大根堆。

所以这个题里面怎么搞呢？当然跑一遍 dijkstra 就不说了关于spfa

先求出对于边的海拔的最大生成树，维护 kruskal 重构树。初始时每个点点权是 $1$ 到它的最短路，合并时新的点点权就是边的两个端点的根节点的点权取 $\min$。那么对于每个询问的点 $v$，找到 $v$ 的所有祖先中海拔大于 $p$ 且深度最小的那一个点 $u$，然后答案就是 $u$ 的点权。

怎么找 $u$ 呢，倍增往上跳就行了。

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

typedef std::pair<int, int> PII;
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int to, nxt, w, a;
} e[800005];
struct Node {
	int u, v, w, a;
	inline bool operator < (const Node x) const {return a > x.a;}//求海拔的最大生成树
} edge[400005];
bool done[200005];
int head[200005], dis[200005], tot, n, m;
int fa[500005], up[500005][20], ans[500005], high[500005];
std::priority_queue<PII, std::vector<PII>, std::greater<PII> > Q;
std::vector<int> sons[500005];
int find(const int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
inline void AddEdge(const int u, const int v, const int w, const int a) {
	e[++ tot].to = v, e[tot].w = w, e[tot].a = a;
	e[tot].nxt = head[u], head[u] = tot;
}

void Dijkstra() {
	memset(dis, 0x3f, sizeof dis);
	memset(done, 0, sizeof done);
	Q.push(std::make_pair(dis[1] = 0, 1));
	while (Q.size()) {
		int u(Q.top().second);
		Q.pop();
		if (done[u]) continue;
		done[u] = true;
		for (int i(head[u]); i; i = e[i].nxt) {
			int v(e[i].to);
			if (dis[u] + e[i].w < dis[v])
				Q.push(std::make_pair(dis[v] = dis[u] + e[i].w, v));
		}
	}
}

void dfs(const int u) {
	for (int i(1); i <= 19; ++ i) up[u][i] = up[up[u][i - 1]][i - 1];
	for (int v : sons[u])
		if (v != up[u][0]) up[v][0] = u, dfs(v);
}
void kruskal() {//重构树的函数
	memset(ans, 0x3f, sizeof ans);
	std::sort(edge + 1, edge + m + 1);
	int cnt(0), k(0), now(n);//k表示当前考虑到了哪条边，cnt表示选了多少边，now表示最后一个新建点的编号
	for (int i(1); i <= n; ++ i) ans[i] = dis[i], fa[i] = i;
	while (cnt < n - 1) {
		++ k;
		int fx(find(edge[k].u)), fy(find(edge[k].v));
		if (fx != fy) {
			++ now, ++ cnt, fa[fx] = fa[fy] = fa[now] = now;
			sons[now].push_back(fx);//将x与y并查集中的根节点作为新建点的儿子
			sons[now].push_back(fy);
			high[now] = edge[k].a;//记录这个点的海拔
			ans[now] = min(ans[fx], ans[fy]);
		}
	}
	dfs(now);
}
int jump(int u, const int p) {
	for (int i(19); ~i; -- i)
		if (up[u][i] && high[up[u][i]] > p) u = up[u][i];
	return ans[u];
}

int main() {
	int T;
	scanf("%d", &T);
	while (T --) {
		memset(head, 0, sizeof head);
		memset(up, 0, sizeof up);
		tot = 0;
		int q, k, s, last(0);
		scanf("%d%d", &n, &m);
		for (int i(1); i <= 2 * n + 1; ++ i) sons[i].clear();
		for (int i(1); i <= m; ++ i) {
			int u, v, w, a;
			scanf("%d%d%d%d", &u, &v, &w, &a);
			AddEdge(u, v, w, a), AddEdge(v, u, w, a);
			edge[i].u = u, edge[i].v = v, edge[i].w = w, edge[i].a = a;
		}
		Dijkstra();//求最短路
		kruskal();//kruskal重构树
		scanf("%d%d%d", &q, &k, &s);
		while (q --) {
			int v, p;
			scanf("%d%d", &v, &p);
			v = (v + k * last - 1) % n + 1;
			p = (p + k * last) % (s + 1);
			printf("%d\n", last = jump(v, p));
		}
	}
	return 0;
}