[NOI2018] 归程

P4768 [NOI2018]归程

Meaning

考虑一张有向无环图上，边存在两种边权 $l,h$。每次查询给定 $u,x$，其中 $u$ 表示起点，$x$ 为限制，求到终点 $1$ ”特殊“ 的最短路长度：在最短路的前半部分，可以经过 $h$ 类边权大于 $x$ 的边，此时边权代价为 $0$；当走过一条 $h$ 类边权小于等于 $x$ 的边后，此后所走过的所有边权代价均为该边的 $w$ 类边权，求最短路距离。强制在线。多组询问。

Sol

首先预处理出所有点到终点 $1$ 的最短路。

考虑按照边权 $h$ 从大到小构建 Kruskal 树，那么我们可以对于查询时给定的起点 $u$ 树上倍增找到第一个 $h$ 不大于 $x$ 点，此时以该点为根结点的子树内的点可以相互到达，那么此时答案即为子树内所有点到终点 $1$ 的最短路的最小值。那么我们考虑通过 dfs 预处理出子树内最短路最小值，即可实现在线查询。

Detail

1. 多组询问，数组一定记得清空。

Code

#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
const int inf = 1e9 + 1e7, MAXN = 6e5 + 1e1;
const lint INF = 1e18 + 1e9;

struct Edge { int nxt, to; lint w; } e[MAXN << 2];
struct edge { int u, v, h; lint w; } c[MAXN];
struct Dot {
    int to; lint w;
    bool friend operator <(const Dot &A, const Dot &B) {
        return A.w > B.w;
    }
} ;
int head[MAXN], ffa[MAXN][20], fa[MAXN], f[MAXN], n, m, q, cnt, tot;
lint dis[MAXN], k, s, lastans;
bool vis[MAXN];
priority_queue <Dot> Q;

void Addedge(int u, int v, lint w) {
    e[++ tot] = (Edge){head[u], v, w}, head[u] = tot;
    return ;
}

int Find(int x) { return (fa[x] == x ? x : fa[x] = Find(fa[x])); }

void Dijstra(void) {
    memset(vis, false, sizeof(vis)), memset(dis, 127, sizeof(dis));
    for (int i = 1; i <= n; i ++) dis[i] = 1ll * inf;
    dis[1] = 0ll, tot = 0, Q.push((Dot){1, 0});
    while (!Q.empty()) {
        int u = Q.top().to; Q.pop();
        if (vis[u]) continue ; vis[u] = true;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to; lint w = e[i].w;
            if (dis[v] > dis[u] + w) dis[v] = dis[u] + w, Q.push((Dot){v, dis[v]});
        }
    }
    return ;
}

void Dfs(int u) {
    for (int i = 1; i <= 19; i ++) ffa[u][i] = ffa[ffa[u][i - 1]][i - 1];
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (ffa[u][0] == v) continue ; ffa[v][0] = u;
        Dfs(v), dis[u] = min(dis[v], dis[u]);
    }
    return ;
}

void Solve() {
    memset(head, 0, sizeof(head)), tot = 0;
    cnt = n = readint, m = readint;
    for (int i = 1; i <= n; i ++) fa[i] = i;
    for (int i = 1; i <= m; i ++) {
        int u = readint, v = readint; lint w = readlint;
        c[i] = (edge){u, v, readint, w};
        Addedge(u, v, w), Addedge(v, u, w);
    }
    Dijstra();
    memset(head, 0, sizeof(head)), memset(ffa, 0, sizeof(ffa));
    sort(c + 1, c + m + 1, [](edge A, edge B){ return (A.h == B.h ? A.w < B.w : A.h > B.h); });
    for (int i = 1; i <= m; i ++) {
        int u = c[i].u, v = c[i].v, w = c[i].h, fu = Find(u), fv = Find(v);
        if (fu != fv) {
            f[++ cnt] = w, fa[cnt] = fa[fu] = fa[fv] = cnt;
            Addedge(fu, cnt, 0ll), Addedge(fv, cnt, 0ll), Addedge(cnt, fu, 0ll), Addedge(cnt, fv, 0ll);
        }
    }
    Dfs(cnt);
    q = readint, k = readlint, s = readlint, lastans = 0ll;
    while (q --) {
        int u = (readint + k * lastans - 1) % (n) + 1;
        lint p = (readlint + k * lastans) % (s + 1ll);
        for (int i = 19; i >= 0; i --) if (ffa[u][i] && f[ffa[u][i]] > p) u = ffa[u][i];
        printf("%lld\n", lastans = dis[u]);
    }
    return ;
}

int main(void) {

    int T = readint;
    while (T --) Solve();

    return 0;
}