代码

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

const int maxn = 600010;
int T, n, m, q, K, S, c, lastans, dist[maxn], fa[maxn];
int dep[maxn], par[maxn][21], mn[maxn][21];
bool vis[maxn];
struct edge {
    int to, l, a;
    bool operator < (const edge &other) const { return l > other.l; }
};
vector<edge> G[maxn], G2[maxn];
struct node {
    int u, v, l, a;
    bool operator < (const node &other) const { return a > other.a; }
} e[maxn];

void dijkstra() {
    priority_queue<edge> q;
    memset(dist, 0x3f, sizeof(dist));
    q.push((edge){1, 0, 0}), dist[1] = 0;
    while (!q.empty()) {
        edge v = q.top(); q.pop();
        for (int i = 0; i < G[v.to].size(); i++) {
            if (dist[G[v.to][i].to] > dist[v.to] + G[v.to][i].l) {
                dist[G[v.to][i].to] = dist[v.to] + G[v.to][i].l;
                q.push((edge){G[v.to][i].to, dist[G[v.to][i].to], 0});
            }
        }
    }
}

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

void dfs(int v, int f) {
    for (int i = 1; (1 << i) <= c; i++) {
        par[v][i] = par[par[v][i - 1]][i - 1];
    }
    for (int i = 1; (1 << i) <= c; i++) {
        mn[v][i] = min(mn[v][i - 1], mn[par[v][i - 1]][i - 1]);
    }
    for (int i = 0; i < G2[v].size(); i++) {
        if (G2[v][i].to == f) continue;
        par[G2[v][i].to][0] = v, mn[G2[v][i].to][0] = G2[v][i].a;
        dep[G2[v][i].to] = dep[v] + 1;
        dfs(G2[v][i].to, v);
        dist[v] = min(dist[v], dist[G2[v][i].to]);
    }
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n * 3; i++) G[i].clear(), G2[i].clear();
        for (int i = 1, u, v, l, a; i <= m; i++) {
            scanf("%d %d %d %d", &u, &v, &l, &a);
            G[u].push_back((edge){v, l, a}), G[v].push_back((edge){u, l, a});
            e[i] = (node){u, v, l, a};
        }
        dijkstra(), sort(e + 1, e + m + 1);
        for (int i = 1; i <= (n << 1); i++) fa[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;
            G2[++c].push_back((edge){u, 0, e[i].a});
            G2[u].push_back((edge){c, 0, e[i].a});
            G2[c].push_back((edge){v, 0, e[i].a});
            G2[v].push_back((edge){c, 0, e[i].a});
            fa[u] = fa[v] = c;
        }
        memset(par, 0, sizeof(par));
        dep[c] = 1, dfs(c, 0);
        scanf("%d %d %d", &q, &K, &S);
        lastans = 0;
        for (int i = 1, v, p; i <= q; i++) {
            scanf("%d %d", &v, &p);
            v = (v + K * lastans - 1) % n + 1, p = (p + K * lastans) % (S + 1);
            for (int j = 20; ~j; j--) {
                if (dep[v] - (1 << j) > 0 && mn[v][j] > p) {
                    v = par[v][j];
                }
            }
            printf("%d\n", lastans = dist[v]);
        }
    }
    return 0;
}

评测结果