NOI2018 - 归程

80pts: 离线的大概就是用并查集按边权从大到小合并，在线的树形图跑一发倍增。。

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> P;

void bye() {
    fprintf(stderr, "%.3lf sec\n", double(clock()) / CLOCKS_PER_SEC);
    exit(0);
}

int gi() {
    int n, c;
    while ((c = getchar()) < '0');
    n = c - '0';
    while ((c = getchar()) >= '0') n = n * 10 + c - '0';
    return n;
}

int bsr(int x) {
    if (x == 0) return -1;
    return 31 - __builtin_clz(x);
}

struct RadixHeap {
    vector<P> v[33];
    int last, sz;
    RadixHeap() {
        last = sz = 0;
    }
    void push(int x, int p) {
        // assert(last <= x);
        sz++;
        v[bsr(x ^ last) + 1].push_back(P(x, p));
    }
    void push(P p) {
        push(p.first, p.second);
    }
    P top() {
        return pop(false);
    }
    P pop(bool f = true) {
        // assert(sz);
        if (!v[0].size()) {
            int i = 1;
            while (!v[i].size()) i++;
            last = min_element(v[i].begin(), v[i].end())->first;
            for (int j = int(v[i].size()) - 1; j >= 0; j--) {
                P& p = v[i][j];
                v[bsr(p.first ^ last) + 1].push_back(p);
            }

            v[i].clear();
        }
        P r = v[0].back();
        if (f) {
            sz--;
            v[0].pop_back();
        }
        return r;
    }
    int size() {
        return sz;
    }
    bool empty() {
        return sz == 0;
    }
    void clear() {
        last = sz = 0;
        for (int i = 0; i < 33; i++) {
            v[i].clear();
        }
    }
};

const int N = 400010;
const int INF = numeric_limits<int>::max();

int tc, n, m;
int X[N], Y[N], A[N], B[N];
int q, K, S;
int V[N], H[N];
// 1-indexed

struct Solve30 {
    int dist[N];
    vector<P> g[N];
    RadixHeap heap;

    void dijkstra(int st) {
        fill(dist + 1, dist + n + 1, INF);
        dist[st] = 0;
        heap.clear();
        heap.push(0, st);
        while (!heap.empty()) {
            int u = heap.pop(true).second;
            int d = dist[u];
            for (int j = int(g[u].size()) - 1; j >= 0; j--) {
                int v = g[u][j].first;
                int w = g[u][j].second + d;
                if (w < dist[v]) {
                    dist[v] = w;
                    heap.push(w, v);
                }
            }
        }
    }

    void solve() {
        for (int i = 1; i <= n; i++) {
            g[i].clear();
        }
        for (int i = 0; i < m; i++) {
            int x = X[i], y = Y[i], z = A[i];
            g[x].push_back(P(y, z));
            g[y].push_back(P(x, z));
        }
        dijkstra(1);

        for (int i = 0; i < q; i++) {
            int v = V[i], h = H[i];
            if (h == 0) puts("0");
            else printf("%d\n", dist[v]);
        }
    }
};

struct SolveSmall {
    static const int N = 1510;

    struct Edge {
        int v, a, b;
        Edge(int v, int a, int b) : v(v), a(a), b(b) {}
    };
    vector<Edge> g[N];
    int dist[N];
    bool reach[N];
    int que[N];
    RadixHeap heap;

   void dijkstra(int st) {
        fill(dist + 1, dist + n + 1, INF);
        dist[st] = 0;
        heap.clear();
        heap.push(0, st);
        while (!heap.empty()) {
            int u = heap.pop(true).second;
            int d = dist[u];
            for (int j = int(g[u].size()) - 1; j >= 0; j--) {
                int v = g[u][j].v;
                int w = g[u][j].a + d;
                if (w < dist[v]) {
                    dist[v] = w;
                    heap.push(w, v);
                }
            }
        }
    }

    void bfs(int st, int rst) {
        que[0] = st;
        int qt = 1;
        fill(reach + 1, reach + n + 1, false);
        reach[st] = true;

        for (int qh = 0; qh < qt; qh++) {
            int u = que[qh];
            for (int j = int(g[u].size()) - 1; j >= 0; j--) {
                int v = g[u][j].v;
                if (reach[v] || g[u][j].b <= rst) continue;
                reach[v] = true;
                que[qt++] = v;
            }
        }
    }

    void solve() {
        for (int i = 1; i <= n; i++) {
            g[i].clear();
        }
        for (int i = 0; i < m; i++) {
            int x = X[i], y = Y[i], a = A[i], b = B[i];
            g[x].push_back(Edge(y, a, b));
            g[y].push_back(Edge(x, a, b));
        }
        dijkstra(1);

        // for (int i = 1; i <= n; i++) {
        //     fprintf(stderr, "%d%c", d1[i], " \n"[i == n]);
        // }

        int lastans = 0;
        for (int i = 0; i < q; i++) {
            int v = (V[i] + 1LL * K * lastans - 1) % n + 1;
            int rst = (H[i] + 1LL * K * lastans) % (S + 1);
            bfs(v, rst);
            int res = INF;
            for (int i = 1; i <= n; i++) {
                if (reach[i]) res = min(res, dist[i]);
            }
            printf("%d\n", res);
            lastans = res;
        }
    }
};

struct SolveTree {
    static const int LG = 20;

    struct Edge {
        int v, a, b;
        Edge(int v, int a, int b) : v(v), a(a), b(b) {}
    };
    vector<Edge> g[N];
    int pr[N][LG], low[N][LG], depth[N];

    void dfs(int u, int p = -1) {
        for (int j = 0; j < LG - 1; j++) {
            if (pr[u][j] == -1) {
                low[u][j + 1] = -1;
                pr[u][j + 1] = -1;
            } else {
                pr[u][j + 1] = pr[pr[u][j]][j];
                low[u][j + 1] = min(low[u][j], low[pr[u][j]][j]);
            }
        }
        for (int j = int(g[u].size()) - 1; j >= 0; j--) {
            int v = g[u][j].v;
            if (v == p) continue;
            int a = g[u][j].a;
            int b = g[u][j].b;
            low[v][0] = b;
            pr[v][0] = u;
            depth[v] = depth[u] + a;
            dfs(v, u);
        }
    }

    int jump(int x, int rst) {
        for (int j = LG - 1; j >= 0; j--) {
            if (low[x][j] > rst) {
                x = pr[x][j];
            }
        }
        return x;
    }

    void solve() {
        for (int i = 0; i < m; i++) {
            int x = X[i], y = Y[i];
            int a = A[i], b = B[i];
            g[x].push_back(Edge(y, a, b));
            g[y].push_back(Edge(x, a, b));
        }
        pr[1][0] = low[1][0] = -1;
        dfs(1);

        int lastans = 0;
        for (int i = 0; i < q; i++) {
            int v = (V[i] + 1LL * K * lastans - 1) % n + 1;
            int rst = (H[i] + 1LL * K * lastans) % (S + 1);
            int dest = jump(v, rst);
            int res = depth[dest];
            printf("%d\n", res);
            lastans = res;
        }
    }
};

struct SolveDSU {
    int dist[N];
    vector<P> g[N];
    RadixHeap heap;
    int par[N], bv[N];
    pair<P, int> qs[N];
    pair<int, P> es[N];
    int res[N];

    void dijkstra(int st) {
        fill(dist + 1, dist + n + 1, INF);
        dist[st] = 0;
        heap.clear();
        heap.push(0, st);
        while (!heap.empty()) {
            int u = heap.pop(true).second;
            int d = dist[u];
            for (int j = int(g[u].size()) - 1; j >= 0; j--) {
                int v = g[u][j].first;
                int w = g[u][j].second + d;
                if (w < dist[v]) {
                    dist[v] = w;
                    heap.push(w, v);
                }
            }
        }
    }

    int root(int x) {
        return x == par[x] ? x : (par[x] = root(par[x]));
    }

    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            par[x] = y;
            bv[y] = min(bv[y], bv[x]);
        }
    }

    void solve() {
        for (int i = 0; i < m; i++) {
            int x = X[i], y = Y[i], a = A[i];
            g[x].push_back(P(y, a));
            g[y].push_back(P(x, a));
        }
        dijkstra(1);

        for (int i = 0; i < q; i++) {
            qs[i] = make_pair(P(H[i], V[i]), i);
        }
        sort(qs, qs + q);

        for (int i = 0; i < m; i++) {
            es[i] = make_pair(B[i], P(X[i], Y[i]));
        }
        sort(es, es + m);

        for (int i = 1; i <= n; i++) {
            par[i] = i;
            bv[i] = dist[i];
        }
        int ei = m - 1;
        for (int i = q - 1; i >= 0; i--) {
            int h = qs[i].first.first;
            int v = qs[i].first.second;
            while (ei >= 0 && es[ei].first > h) {
                unite(es[ei].second.first, es[ei].second.second);
                ei--;
            }
            // fprintf(stderr, "solving (%d %d), ei = %d, qi = %d\n", h, v, ei, qs[i].second);
            // if (ei < 0) assert(root(v) == root(1));
            res[qs[i].second] = bv[root(v)];
        }
        for (int i = 0; i < q; i++) {
            printf("%d\n", res[i]);
        }
    }
}; 

int main() {
    // freopen("return.in", "r", stdin);
    // freopen("return.out", "w", stdout);

    scanf("%d", &tc);
    for (int t = 1; t <= tc; t++) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < m; i++) {
            X[i] = gi();
            Y[i] = gi();
            A[i] = gi();
            B[i] = gi();
        }
        scanf("%d %d %d", &q, &K, &S);
        for (int i = 0; i < q; i++) {
            V[i] = gi();
            H[i] = gi();
        }

        bool case30 = (K == 0);
        for (int i = 0; i < m && case30; i++) {
            case30 &= (B[i] == 1);
        }
        if (case30) {
            // fprintf(stderr, "solving 30\n");
            (new Solve30)->solve();
            continue;
        }

        bool small = (n <= 1500);
        if (small) {
            // fprintf(stderr, "solving small\n");
            (new SolveSmall)->solve();
            continue;
        }

        bool tree = (m == n - 1);
        if (tree) {
            // fprintf(stderr, "solving tree\n");
            (new SolveTree)->solve();
            continue;
        }

        bool rest = (K == 0);
        if (rest) {
            // fprintf(stderr, "solving offline\n");
            (new SolveDSU)->solve();
            continue;
        }

        // 80pts?

        (new SolveSmall)->solve();
    }

    // fprintf(stderr, "%.3lf sec\n", double(clock()) / CLOCKS_PER_SEC);
    return 0;
}#inc