代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 6e5 + 10;

struct E {
    int u, v, l, a;
    bool operator < (const E& A) const { return a > A.a; }
} e[maxn];

struct Edge {
    Edge* next;
    int to, w;
    Edge(Edge* next = 0, int to = 0, int w = 0): next(next), to(to), w(w) {}
} *first[maxn], *f2[maxn];

int n, m, f[maxn], d[maxn], vis[maxn], de[maxn], c, q, k, s, vi[maxn][20], pi[maxn][20];

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

struct Node {
    int u, w;
    Node(int u = 0, int w = 0): u(u), w(w) {}
    bool operator < (const Node& A) const { return w > A.w; }
};

void Dijkstra() {
    priority_queue<Node> Q; Q.push(Node(1, 0));
    memset(d, 0x3f, sizeof d), d[1] = 0;
    memset(vis, 0, sizeof vis);
    while (!Q.empty()) {
        Node x = Q.top(); Q.pop();
        if (vis[x.u]) continue;
        vis[x.u] = 1;
        for (Edge* now = first[x.u]; now; now = now->next) {
            if (d[now->to] > d[x.u] + now->w) {
                d[now->to] = d[x.u] + now->w;
                Q.push(Node(now->to, d[now->to]));
            }
        }
    }
}

void Add(int u, int v, int w) {
    f2[u] = new Edge(f2[u], v, w);
    f2[v] = new Edge(f2[v], u, w);
}

void Dfs(int u, int pa) {
    for (int i = 1; (1 << i) <= c; i++) pi[u][i] = pi[pi[u][i - 1]][i - 1];
    for (int i = 1; (1 << i) <= c; i++) vi[u][i] = min(vi[u][i - 1], vi[pi[u][i - 1]][i - 1]);
    for (Edge* now = f2[u]; now; now = now->next) {
        if (now->to == pa) continue;
        pi[now->to][0] = u, vi[now->to][0] = now->w;
        de[now->to] = de[u] + 1, Dfs(now->to, u);
        d[u] = min(d[u], d[now->to]);
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        memset(first, 0, sizeof first);
        memset(f2, 0, sizeof f2);
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++) {
            scanf("%d%d%d%d", &e[i].u, &e[i].v, &e[i].l, &e[i].a);
            first[e[i].u] = new Edge(first[e[i].u], e[i].v, e[i].l);
            first[e[i].v] = new Edge(first[e[i].v], e[i].u, e[i].l);
        }
        Dijkstra();
        sort(e + 1, e + 1 + m);
        for (int i = 1; i <= n << 1; i++) f[i] = i;
        c = n;
        for (int i = 1; i <= m; i++) {
            int u = find(e[i].u), v = find(e[i].v);
            if (u == v) continue;
            Add(++c, u, e[i].a), Add(c, v, e[i].a);
            f[u] = f[v] = c;
        }
        memset(pi, 0, sizeof pi);
        de[c] = 1, Dfs(c, 0);
        int ans = 0;
        scanf("%d%d%d", &q, &k, &s);
        while (q--) {
            int v, p; scanf("%d%d", &v, &p);
            v = (v + k * ans - 1) % n + 1;
            p = (p + k * ans) % (s + 1);
            for (int i = 19; ~i; i--) {
                if (de[v] - (1 << i) > 0 && vi[v][i] > p) {
                    v = pi[v][i];
                }
            }
            printf("%d\n", ans = d[v]);
        }
    }
    return 0;
}

评测结果