代码

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

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> void write(T x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
template <typename T> void writeln(T x) {
    write(x);
    puts("");
}
template <typename T> inline bool chkMin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkMax(T& x, const T& y) { return x < y ? (x = y, true) : false; }
#ifdef WIN32
#define LLIO "%I64d"
#else
#define LLIO "%lld"
#endif	// WIN32 long long
#define rep(I, A, B) for (int I = (A); I <= (B); ++I)
#define dwn(I, A, B) for (int I = (A); I >= (B); --I)
#define erp(I, X) for (int I = head[X]; I; I = next[I])

const int maxn = 4e5 + 207, inf = INT_MAX;
struct Edge {
    int x, y, l, h;
    Edge(int f, int t, int len, int hei)
        : x(f), y(t), l(len), h(hei) {}
    Edge() : x(0), y(0), l(0), h(0) {}
};
Edge e[maxn];
struct Graph {
    int v[maxn << 1], len[maxn << 1], hei[maxn << 1], next[maxn << 1], head[maxn];
    int tot;
    void ae(int x, int y, int l, int h) {
        v[++tot] = y; len[tot] = l; hei[tot] = h; next[tot] = head[x]; head[x] = tot;
    }
};
Graph G, T;
int fa[maxn], height[maxn], dist[maxn], f[30][maxn];
int n, m, test, xys;

inline void clear() {
    rep(i, 1, (n << 1)) height[i] = 0;
    rep(i, 0, 25) rep(j, 1, (n << 1)) f[i][j] = 0;
}

struct CmpType {
    bool operator()(const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) {
        return lhs.second > rhs.second;
    }
};
inline void dijkstra() {
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, CmpType> q;
    q.push(std::make_pair(1, 0));
    rep(i, 2, n) dist[i] = inf;
    while (!q.empty()) {
        std::pair<int, int> x = q.top(); q.pop();
        if (x.second != dist[x.first]) continue;
        for (int i = G.head[x.first]; i; i = G.next[i]) {
            int v = G.v[i], w = G.len[i];
            if (dist[v] > dist[x.first] + w)
                q.push(std::make_pair(v, dist[v] = dist[x.first] + w));
        }
    }
}
inline bool higher(const Edge& lhs, const Edge& rhs) {
    return lhs.h > rhs.h;
}
int findf(int x) { return fa[x] == x ? x : (fa[x] = findf(fa[x])); }
inline void kruskal() {
    rep(i, 1, (n << 1)) fa[i] = i;
    xys = n;
    std::sort(e + 1, e + m + 1, higher);
    T.tot = 0;
    rep(i, 1, (n << 1)) T.head[i] = 0;
    rep(i, 1, m) {
        int x = e[i].x, y = e[i].y, w = e[i].h;
        int fx = findf(x), fy = findf(y);
        if (fx != fy) {
            fa[fx] = fa[fy] = ++xys;
            T.ae(xys, fx, 0, 0);
            T.ae(xys, fy, 0, 0);
            height[xys] = w;
            dist[xys] = std::min(dist[fx], dist[fy]);
        }
    }
}
void dfs(int x) {
    rep(i, 1, 25) f[i][x] = f[i - 1][f[i - 1][x]];
    for (int i = T.head[x]; i; i = T.next[i]) {
        f[0][T.v[i]] = x;
        dfs(T.v[i]);
    }
}
inline int query(int v, int p) {
    dwn(i, 25, 0) if (height[f[i][v]] > p) v = f[i][v];
    return dist[v];
}

int main() {
    read(test);
    while (test--) {
        read(n); read(m);
        G.tot = 0;
        rep(i, 1, n) G.head[i] = 0;
        rep(i, 1, m) {
            int x, y, l, h;
            read(x); read(y); read(l); read(h);
            G.ae(x, y, l, h);
            G.ae(y, x, l, h);
            e[i] = Edge(x, y, l, h);
        }
        dijkstra();
        kruskal();
        dfs(xys);
        int q, k, s;
        read(q); read(k); read(s);
        int lastans = 0;
        while (q--) {
            int v, p; read(v); read(p);
            v = (v + k * lastans - 1) % n + 1;
            p = (p + k * lastans) % (s + 1);
            writeln(lastans = query(v, p));
        }
        clear();
    }
    return 0;
}

评测结果