P4768 归程 做题记录

· · 个人记录

一道名扬四海的题，当然不是因为它有多好或者多难，而是——它卡了 SPFA。

但是实际上这道题也不差，是一道练习 Kruskal重构树 的好题，所以写了这篇做题记录，也是我第一道边做题边写做题记录来整理思路的题。

首先我们看到题干，每条边有两个信息：海拔和长度，每次会给定海拔的下限，要求出从给定点到点 1 的路径中海拔比给定下限低的边的长度和的最小值。

这道题乍一看并不好做，如果暴力只能拿 44 分，而且正解还要求强制在线，所以可以想到要用一些特殊的知识，我们可以预处理出每个点到点 1 的最短路，这可以跑 dijkstra，当然也可以用 SPFA，不过结果会变成 100->60&&Au->Ag 就是了。

求出最短路后我们可以发现：有海拔大于当前给定值的点可以随意走，也就是说这几个点的最短路都是其中最小的最短路，但是我们该怎么维护呢。并不可以想到，我们可以用 Kruskal重构树，它的性质是两个点之间的最小/大边权就是这两个点的 LCA，那我们可以按海拔最大值排序，建出一棵 Kruskal重构树 然后每次找到给定的点的祖先中点权是大于给定海拔的最小值，然后这个祖先的子树就是给定的点能开车驶到的点，它们中最小的最短路就是答案。

所以步骤是先 dijkstra 再 Kruskal重构树 然后找到那个点权大于海拔且最小的点，找它子树的最短路中的最小值，这个可以再建完树就 dfs 找到。但是问题就在于怎么找点，这个问题我们想到可以用 树上倍增 暴力往上跳！结果吃满 O(n) 复杂度再次挂分，但我们可以用树上倍增逐渐往上跳，是 O(logn) 的，这样就没问题，最后处理主函数就行了，另外这道题开始要建双向边，别问我怎么知道的，另外这道题细节不少，要多小心。

六分钟后的我："啊啊啊啊啊啊啊啊啊啊！（战吼起手）我是唐诗！"一定要记住把每个点的 fa 数组先设为它自己（就是并查集那个 fa）。这是血的教训，另外还有记录当前节点有几个的 k 开始一定要设为 n，另另外，是海拔 不超过 给定海拔，也就是说是小于等于。另另另外，多测不清空，亲人两行泪，清空不清前向星，RE 到不自知。

代码（最优解是四秒多，我是最优解的二点五倍骄傲 ）：

//Just Sayori
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define ll long long
#define rnt register int
#define N 600005
#define M 1000000007
using namespace std;
inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
struct edge
{
    int u, v, w, a, next;
} e[N << 1];
struct node
{
    int v, next;
} _e[N << 2];
int head[N], _head[N], cnt, _cnt;
inline bool cmp(edge aa, edge bb)
{
    return aa.a > bb.a;
}
inline void tdd(int u, int v, int l, int a)
{
    e[++cnt] = {u, v, l, a, head[u]}, head[u] = cnt;
    e[++cnt] = {v, u, l, a, head[v]}, head[v] = cnt;
}
inline void add(int u, int v)
{
    _e[++_cnt] = {v, _head[u]}, _head[u] = _cnt;
}
int n, m, k, l, p, last;
int w[N], fa[N], deep[N];
int _fa[N][25];
ll d[N];
bool vis[N];
int find(int a)
{
    return fa[a] == a ? a : fa[a] = find(fa[a]);
}
void kruskal()
{
    int tot = 0, fu, fv;
    sort(e + 1, e + 2 * m + 1, cmp);
    for (rnt i = 1; i <= 2 * m; i++)
    {
        if (tot == n - 1) break;
        fu = find(e[i].u), fv = find(e[i].v);
        if (fu == fv) continue;
        k++, fa[k] = k, fa[fv] = k, fa[fu] = k, tot++;
        add(k, fu), add(k, fv), w[k] = e[i].a;
    }
}
void dfs(int u, int f)
{
    _fa[u][0] = f;
    deep[u] = deep[f] + 1;
    for (rnt i = 1; i <= 20; i++)
        _fa[u][i] = _fa[_fa[u][i - 1]][i - 1];
    for (rnt i = _head[u]; i; i = _e[i].next)
    {
        int v = _e[i].v;
        if (v == f) continue;
        dfs(v, u);
        d[u] = min(d[u], d[v]);
    }
}
void dijk()
{
    int u;
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    priority_queue<pair<ll, int>>q;
    q.push(make_pair(0, 1));
    while (!q.empty())
    {
        u = q.top().second, q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (rnt i = head[u]; i; i = e[i].next)
        {
            int v = e[i].v;
            if (d[v] > d[u] + e[i].w)
            {
                d[v] = d[u] + e[i].w;
                if (!vis[v])
                    q.push(make_pair(-d[v], v));
            }
        }
    }
}
ll query(int u, int v)
{
    for (rnt i = 20; i >= 0; i--)
        if (deep[u] - (1 << i) > 0 && w[_fa[u][i]] > v)
            u = _fa[u][i];
    return d[u];
}
int get_u(int u)
{
    return (u + l *last - 1) % n + 1;
}
int get_v(int v)
{
    return (v + l *last) % (p + 1);
}
int main()
{
    int t = read(), u, v;
    while (t--)
    {
        cnt = 0, _cnt = 0, last = 0;
        memset(w, 0, sizeof w);
        memset(fa, 0, sizeof fa);
        memset(_fa, 0, sizeof _fa);
        memset(vis, 0, sizeof vis);
        memset(head, 0, sizeof head);
        memset(_head, 0, sizeof _head);
        n = read(), m = read(), k = n;
        for (rnt i = 1; i <= m; i++)
            u = read(), v = read(), l = read(), p = read(), tdd(u, v, l, p);
        for (rnt i = 1; i <= n; i++) fa[i] = i;
        dijk(), kruskal(), dfs(k, 0);
        m = read(), l = read(), p = read();
        for (rnt i = 1; i <= m; i++)
            u = get_u(read()), v = get_v(read()), last = query(u, v), printf("%lld\n", last);
    }
    return 0;
}