代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cctype>

using namespace std;

int Read() {
    char c;
    while (c = getchar(), !isdigit(c));
    int x = c - 48;
    while (c = getchar(), isdigit(c)) x = x * 10 + c - 48;
    return x;
}

void Write(int x) {
    int a[10], k = 0;
    do a[++k] = x % 10;
    while (x /= 10);
    while (k) putchar(a[k--] + 48);
    putchar('\n');
    return;
}

typedef pair<int, int> PII;

#define fi first
#define se second
#define mp make_pair

const int N = 200010, M = 400010;

int n, m, q, k, s;
int tot, head[N];
struct Edge {
    int p, nxt, w;
    Edge(int p = 0, int nxt = 0, int w = 0) : p(p), nxt(nxt), w(w) {}
} edge[M * 2];
inline void Add(int u, int v, int w) {
    edge[++tot] = Edge(v, head[u], w);
    head[u] = tot;
    return;
}
void Init() {
    tot = -1;
    memset(head, -1, sizeof(head));
    return;
}
struct Node {
    int u, v, w;
    bool operator < (const Node &a) const {
        return w < a.w;
    }
} a[M];

vector<int> va;

priority_queue<PII> pq;
int d[N];

void Dijkstra() {
    memset(d, 0x3f, sizeof(d));
    pq.push(mp(-(d[1] = 0), 1));
    while (!pq.empty()) {
        PII cur = pq.top();
        pq.pop();
        int u = cur.se;
        if (d[u] < -cur.fi) continue;
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].p, w = edge[i].w;
            if (d[v] > d[u] + w) pq.push(mp(-(d[v] = d[u] + w), v));
        }
    }
    return;
}

namespace ST {

    struct Info {
        int fa, md;
        Info(int fa = 0, int md = 0) : fa(fa), md(md) {}
    };
    int tot;
    struct Node {
        int lc, rc, l, r;
        Info info;
    } p[N * 4 + M * 40];
    void Init() {
        tot = 0;
        return;
    }

    void Build(int &k, int l, int r) {
        k = ++tot;
        p[k].l = l;
        p[k].r = r;
        if (l == r) {
            p[k].info = Info(l, d[l]);
            return;
        }
        int m = (l + r) / 2;
        Build(p[k].lc, l, m);
        Build(p[k].rc, m + 1, r);
        return;
    }

    void Modify(int &k, int _k, int x, Info info) {
        p[k = ++tot] = p[_k];
        if (p[k].l == p[k].r) {
            p[k].info = info;
            return;
        }
        if (x <= p[p[k].lc].r) Modify(p[k].lc, p[_k].lc, x, info);
        else Modify(p[k].rc, p[_k].rc, x, info);
        return;
    }

    Info Query(int k, int x) {
        if (p[k].l == p[k].r) return p[k].info;
        if (x <= p[p[k].lc].r) return Query(p[k].lc, x);
        return Query(p[k].rc, x);
    }
    
}

ST::Info Gf(int v, int k) {
    ST::Info info = ST::Query(v, k);
    if (k == info.fa) return info;
    return Gf(v, info.fa);
}

int f[N], size[N], md[N];
int Gf(int k) {
    return (f[k] != k) ? (f[k] = Gf(f[k])) : k;
}

int root[M];

void Solve() {
    scanf("%d%d", &n, &m);
    Init();
    va.clear();
    for (int i = 1; i <= m; ++i) {
        int u = Read(), v = Read(), l = Read(), a = Read();
        //int u, v, l, a;
        //scanf("%d%d%d%d", &u, &v, &l, &a);
        Add(u, v, l);
        Add(v, u, l);
        ::a[i].u = u;
        ::a[i].v = v;
        ::a[i].w = a;
        va.push_back(a);
    }
    sort(a + 1, a + m + 1);
    sort(va.begin(), va.end());
    va.erase(unique(va.begin(), va.end()), va.end());
    Dijkstra();
    int t = va.size();
    ST::Init();
    ST::Build(root[t], 1, n);
    for (int i = 1; i <= n; ++i) {
        f[i] = i;
        size[i] = 1;
        md[i] = d[i];
    }
    for (int i = t - 1, j = m; ~i; --i) {
        root[i] = root[i + 1];
        for (; j && a[j].w >= va[i]; --j) {
            int x = Gf(a[j].u), y = Gf(a[j].v);
            if (x != y) {
                if (size[x] < size[y]) swap(x, y);
                f[y] = x;
                size[x] += size[y];
                md[x] = min(md[x], md[y]);
                ST::Modify(root[i], root[i], y, ST::Info(x, md[y]));
                ST::Modify(root[i], root[i], x, ST::Info(x, min(md[x], md[y])));
            }
        }
    }
    int q, k, s, la = 0;
    scanf("%d%d%d", &q, &k, &s);
    while (q--) {
        int v = Read(), p = Read();
        //int v, p;
        //scanf("%d%d", &v, &p);
        v = (v + k * la - 1) % n + 1;
        p = (p + k * la) % (s + 1);
        int j = upper_bound(va.begin(), va.end(), p) - va.begin();
        la = Gf(root[j], v).md;
        Write(la);
        //printf("%d\n", la);
    }
    return;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) Solve();
    return 0;
}

评测结果