代码

#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <queue>
#include <vector>
#include <utility>

template <typename T> inline void read(T& t) {
    int f = 0, c = getchar(); t = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
    if (f) t = -t;
}
template <typename T, typename... Args>
inline void read(T& t, Args&... args) {
    read(t); read(args...);
}

#define rep(I, A, B) for (int I = (A); I <= (B); ++I)
#define rrep(I, A, B) for (int I = (A); I >= (B); --I)
#define erep(I, X) for (int I = head[X]; I; I = next[I])

struct Edge {
    int from, to, len, height;
    Edge() : from(0), to(0), len(0), height(0) {}
    explicit Edge(int f, int t, int l, int h) : from(f), to(t), len(l), height(h) {}
};
inline bool operator<(const Edge& lhs, const Edge& rhs) {
    return lhs.height < rhs.height;
}

const int maxn = 4e5 + 100;
int fa[maxn * 30], dep[maxn * 30], left[maxn * 30], right[maxn * 30], mindist[maxn * 30];
int root[maxn];
int dist[maxn];
int mv[maxn << 2], mp[maxn << 2], M;
int v[maxn << 1], next[maxn << 1], len[maxn << 1], height[maxn << 1], head[maxn];
Edge edges[maxn << 1];
int tmp[maxn];
int n, m, tot, etot;
int Q, K, S, T, lastans;

inline void clear() {
    rep(i, 1, tot) fa[i] = dep[i] = left[i] = right[i] = 0, mindist[i] = INT_MAX;
    rep(i, 1, n) dist[i] = INT_MAX, head[i] = 0;
    rep(i, 1, etot) v[i] = next[i] = len[i] = height[i] = 0;
    rep(i, 1, m) edges[i] = Edge(), tmp[i] = 0;
    rep(i, 1, (M << 1) - 1) mv[i] = mp[i] = 0;
    tmp[m + 1] = 0;
    n = m = tot = etot = Q = K = S = lastans = 0;
}
inline void ae(int x, int y, int l, int h) {
    v[++etot] = y;
    len[etot] = l;
    height[etot] = h;
    next[etot] = head[x];
    head[x] = etot;
}

inline void update(int x) {
    mv[x] = std::min(mv[x << 1], mv[x << 1 | 1]);
    mp[x] = mv[x << 1] < mv[x << 1 | 1] ? mp[x << 1] : mp[x << 1 | 1];
}
inline void buildTree() {
    for (M = 1; M < n + 2; M <<= 1);
    rep(i, M, (M << 1) - 1) mv[i] = (mp[i] = i - M) == 1 ? 0 : INT_MAX;
    rrep(i, M - 1, 1) update(i);
}
inline void modify(int x, int nv) {
    for (mv[x += M] = nv, x >>= 1; x; update(x), x >>= 1);
}
inline void dijkstra() {
    rep(i, 1, n) dist[i] = INT_MAX;
    dist[1] = 0; buildTree();
    while (mv[1] < INT_MAX) {
        int x = mp[1]; modify(x, INT_MAX);
        erep(i, x) if (dist[v[i]] > dist[x] + len[i])
            modify(v[i], dist[v[i]] = dist[x] + len[i]);
    }
}

void build(int &curr, int l, int r) {
    curr = ++tot;
    if (l == r) {
        fa[curr] = l;
        dep[curr] = 1;
        mindist[curr] = dist[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(left[curr], l, mid);
    build(right[curr], mid + 1, r);
}
int insert(int& curr, int pre, int l, int r, int pos) {
    curr = ++tot;
    if (l == r) return curr;
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        right[curr] = right[pre];
        return insert(left[curr], left[pre], l, mid, pos);
    } else {
        left[curr] = left[pre];
        return insert(right[curr], right[pre], mid + 1, r, pos);
    }
}
inline int findfa(int v, int x) {
    int curr = root[v];
    while (0207) {
        curr = root[v];
        int l = 1, r = n;
        while (l != r) {
            int mid = (l + r) >> 1;
            if (x <= mid) {
                r = mid;
                curr = left[curr];
            } else {
                l = mid + 1;
                curr = right[curr];
            }
        }
        if (fa[curr] == x) break;
        x = fa[curr];
    }
    return curr;
}

int main() {
    // freopen("return5.in", "r", stdin);
    // freopen("return5.out", "w", stdout);
    read(T);
    while (T--) {
        read(n, m);
        rep(i, 1, m) {
            int x, y, l, h;
            read(x, y, l, h);
            ae(x, y, l, h);
            ae(y, x, l, h);
            edges[i] = Edge(x, y, l, h);
        }
        dijkstra();

        read(Q, K, S);
        std::sort(edges + 1, edges + m + 1);
        rep(i, 1, m) tmp[i] = edges[i].height;
        tmp[m + 1] = S + 1;
        int all = std::unique(tmp + 1, tmp + m + 2) - (tmp + 1);

        build(root[all], 1, n);

        int j = m;
        rrep(i, all - 1, 1) {
            root[i] = root[i + 1];
            while (j && edges[j].height == tmp[i]) {
                int x = edges[j].from;
                int y = edges[j].to;
                int fx = findfa(i, x);
                int fy = findfa(i, y);

                if (fa[fx] != fa[fy]) {
                    if (dep[fx] > dep[fy]) std::swap(fx, fy);
                    fa[insert(root[i], root[i], 1, n, fa[fx])] = fa[fy];
                    int z = insert(root[i], root[i], 1, n, fa[fy]);
                    fa[z] = fa[fy];
                    mindist[z] = std::min(mindist[fx], mindist[fy]);
                    dep[z] = dep[fy];
                    if (dep[fx] == dep[fy])
                        ++dep[z];
                }

                --j;
            }

        }
        while (Q--) {
            int ss, p;
            read(ss, p);
            ss = (ss + K * lastans - 1) % n + 1;
            p = (p + K * lastans) % (S + 1);
            int version = std::upper_bound(tmp + 1, tmp + all + 1, p) - tmp;
            int fs = findfa(version, ss);
            printf("%d\n", mindist[fs]);
            lastans = mindist[fs];
        }
        clear();
    }
    return 0;
}

评测结果