Luogu4768 [NOI2018]归程

发布于 15 天前  27 次阅读


Link

Description

n 个点,m 条边, 保证图联通, 每条边有两个权值, 一个长度, 一个海拔, 多组询问, 告诉你起点和水位线, 小于等于水位线的边都会被淹没, 只能走路, 否则可以开车, 问从当天起点到 1 号节点最少步行经过的长度, 强制在线.

Sol

现在每条边都有两个限制,一个是水位线 h,另外一个是距离 v. 因为你从一个地方被水淹没以后你只能下车步行。为了满足这个限制,就可以弄一棵Kruskal重构树出来,在这个上面倍增往上跳,直到被水淹没就下车走。所以预处理从 1 号点到每个点的最短距离,然后倍增预处理的时候记一下你这个子树里面最小的距离就可以了。

感觉这篇题解有一句话题解的意味...

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 4e5 + 5;
const int SIZE_M = 8e5 + 5;
const int inf = 0x7f7f7f7f;

int T, n, m, q, num, tot, num1;
int head[SIZE], dis[SIZE], vis[SIZE], fa[SIZE], val[SIZE], f[SIZE][25], w[SIZE];

struct node {
    int to, v, nxt;
} edge[SIZE_M << 1];

struct g {
    int from, to, v;
} e[SIZE_M << 1];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

inline void addEdge(int u, int v, int d)
{
    edge[++ num].to = v, edge[num].v = d, edge[num].nxt = head[u];
    head[u] = num;
}

inline int cmp(g a, g b) { return a.v > b.v; }

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

inline void dijkstra()
{
    std::priority_queue < pair < int, int > > q;
    memset(dis, inf, sizeof(dis));
    dis[1] = 0, q.push(make_pair(0, 1));
    while (!q.empty()) {
        int u = q.top().second, v;
        q.pop();
        if (vis[u]) continue; vis[u] = 1;
        for (int i = head[u]; i; i = edge[i].nxt) {
            v = edge[i].to;
            if (dis[v] > dis[u] + edge[i].v) {
                dis[v] = dis[u] + edge[i].v;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
}

inline void dfs(int u, int fa)
{
    val[u] = dis[u];
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (v == fa) continue;
        f[v][0] = u;
        for (int j = 1; j <= 24; ++ j) f[v][j] = f[f[v][j - 1]][j - 1];
        dfs(v, u);
        val[u] = std::min(val[u], val[v]);
    }
}   

inline void kruskal()
{
    std::sort(e + 1, e + num1 + 1, cmp);
    memset(head, 0, sizeof(head)); num = 1;
    for (int i = 1; i <= n; ++ i) fa[i] = i;
    for (int i = 1; i <= num1; ++ i) {
        int fu = find(e[i].from), fv = find(e[i].to);
        if (fu != fv) {
            w[++ tot] = e[i].v;
            fa[tot] = fa[fu] = fa[fv] = tot;
            addEdge(tot, fu, 0); /* addEdge(fu, tot, 0);*/
            addEdge(tot, fv, 0); /* addEdge(fv, tot, 0); */
        }
    }
    dfs(tot, 0);
}

inline void init()
{
    num1 = num = tot = 0;
    memset(head, 0, sizeof(head));
    memset(vis, 0, sizeof(vis));
    memset(val, 0, sizeof(val));
    memset(f, 0, sizeof(f));
    memset(w, 0, sizeof(w));
}

signed main()
{
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    T = read();
    while (T --) {
        n = read(), m = read(); tot = n;
        for (int i = 1, u, v, d, h; i <= m; ++ i) {
            u = read(), v = read(), d = read(), h = read();
            addEdge(u, v, d); addEdge(v, u, d);
            e[++ num1].from = u, e[num1].to = v, e[num1].v = h;
        }
        dijkstra();
        kruskal();
        int q = read(), k = read(), s = read(), lastans = 0;
        while (q --) {
            int vi = read(), pi = read();
            int v = (vi + k * lastans - 1) % n + 1, p = (pi + k * lastans) % (s + 1);
            for (int j = 24; j >= 0; -- j) {
                if (f[v][j] && w[f[v][j]] > p) {
                    v = f[v][j];
                }
            }
            printf("%lld\n",lastans = val[v]);
        }
        init();
    }
    return 0;
}

朴实沉毅