BZOJ5415【NOI2018】归程 < 最短路+Kruskal重构树+DFS序+线段树 >

Problem

标签：最短路径 Kruskal重构树 DFS序 线段树

Solution

这道题和BZOJ3551【ONTAK2010】Peaks加强版几乎相同。
预处理跑一遍，可得到每个点到终点的最短距离，将这个距离作为权值，就和一样了。
建重构树，用线段树维护序即可。

Code

#include <bits/stdc++.h>
#define LOG 20
#define MAX_N 400000
#define INF 2147483647
#define fir first
#define sec second
#define mid ((s+t)>>1)
using namespace std;
typedef pair<int,int> pii;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int N, M, Q, K, S;
int anc[MAX_N+5][LOG+1], dep[MAX_N+5];
vector <int> G[MAX_N+5], g[2][MAX_N+5];
int h[MAX_N+5], fa[MAX_N+5], tr[MAX_N<<2];
int cnt, ind, id[MAX_N+5], into[MAX_N+5], outo[MAX_N+5];
struct edge {int u, v, c;} E[MAX_N+5];
void addedge(int u, int v) {G[u].push_back(v);}
bool cmp(const edge &a, const edge &b) {return a.c > b.c;}
int getf(int x) {return fa[x] == x ? x : fa[x] = getf(fa[x]);}
void Dijkstra() {
    h[0] = 0; for (int i = 1; i <= N; i++) h[i] = INF;
    priority_queue <pii> que; que.push(pii((h[1] = 0), 1));
    while (!que.empty()) {
        int u = que.top().sec, d = que.top().fir;
        que.pop(); if (h[u] != -d) continue;
        for (int i = 0, v; i < (int)g[0][u].size(); i++)
            if (h[u]+g[1][u][i] < h[v = g[0][u][i]])
                h[v] = h[u]+g[1][u][i], que.push(pii(-h[v], v));
    }
}
void Kruskal() {
    cnt = 1, sort(E+1, E+M+1, cmp);
    for (int i = 1; i <= N; i++) fa[i] = i;
    for (int i = 1; i <= M && cnt < N; i++) {
        int u = getf(E[i].u), v = getf(E[i].v);
        if (u^v)
            fa[cnt+N] = cnt+N, fa[u] = fa[v] = cnt+N, 
            addedge(cnt+N, u), addedge(cnt+N, v), 
            h[cnt+N] = E[i].c, cnt++;
    }
}
void DFS(int u) {
    into[u] = ++ind, id[ind] = u;
    for (int i = 1; i <= LOG; i++)
        anc[u][i] = anc[anc[u][i-1]][i-1];
    for (int i = 0, v; i < (int)G[u].size(); i++)
        anc[v = G[u][i]][0] = u, dep[v] = dep[u]+1, DFS(v);
    outo[u] = ind;
}
void modify(int v, int s, int t, int p, int x) {
    if (s == t) {tr[v] = x; return;}
    if (p <= mid) modify(v<<1, s, mid, p, x);
    if (p >= mid+1) modify(v<<1|1, mid+1, t, p, x);
    tr[v] = min(tr[v<<1], tr[v<<1|1]);
}
int query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return tr[v]; int ret = INF;
    if (l <= mid) ret = min(ret, query(v<<1, s, mid, l, r));
    if (r >= mid+1) ret = min(ret, query(v<<1|1, mid+1, t, l, r));
    return ret;
}
int getans(int u, int c) {
    for (int i = LOG; ~i; i--)
        if (h[anc[u][i]] > c) u = anc[u][i];
    return query(1, 1, N+N, into[u], outo[u]);
}
int main() {
    int T; read(T);
    while (T--) {
        read(N), read(M);
        for (int i = 1; i <= N; i++)
            g[0][i].clear(), g[1][i].clear();
        for (int i = 1; i <= N+N; i++) G[i].clear();
        memset(tr, 0, sizeof tr), memset(anc, 0, sizeof anc);
        for (int i = 1, u, v, c, h; i <= M; i++)
            read(u), read(v), read(c), read(h), 
            g[0][u].push_back(v), g[1][u].push_back(c), 
            g[0][v].push_back(u), g[1][v].push_back(c), 
            E[i] = (edge){u, v, h};
        Dijkstra(), Kruskal(), ind = 0, DFS(getf(1));
        for (int i = 1, p; i < N+N; i++)
            if ((p = id[i]) <= N) modify(1, 1, N+N, into[p], h[p]);
            else modify(1, 1, N+N, into[p], INF);
        read(Q), read(K), read(S);
        for (int i = 1, lst = 0; i <= Q; i++) {
            int u, c; read(u), read(c);
            u = (u+K*lst-1)%N+1, c = (c+K*lst)%(S+1);
            printf("%d\n", lst = getans(u, c));
        }
    }
    return 0;
}