代码

// This code is AI-generated. (AI 生成的代码)
// NOI2018 归程: Dijkstra from 1 for walking distances; Kruskal reconstruction
// tree over edges sorted by altitude (descending); binary lifting finds the
// highest ancestor with altitude > p, whose subtree min dist is the answer.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
enum { MAXN = 200005, MAXM = 400005, LOG = 19 };
struct Edge { int u, v, l, a; } E[MAXM];
static bool cmpA(const Edge &x, const Edge &y) { return x.a > y.a; }
static int hd[MAXN], nx[2 * MAXM], to[2 * MAXM], wt[2 * MAXM], ec;
static ll dist[MAXN];
static int fa[2 * MAXN], lc[2 * MAXN], rc[2 * MAXN], alt[2 * MAXN];
static int up[LOG][2 * MAXN];
static ll mind[2 * MAXN];
static int heap_node[2 * MAXM];
static ll heap_key[2 * MAXM];
static int hn;
static void hpush(int u, ll key) {
    int i = hn++;
    while (i) { int p = (i - 1) >> 1; if (heap_key[p] <= key) break; heap_key[i] = heap_key[p]; heap_node[i] = heap_node[p]; i = p; }
    heap_key[i] = key; heap_node[i] = u;
}
static int hpop(ll &key) {
    int r = heap_node[0]; key = heap_key[0];
    int n = --hn; ll lk = heap_key[n]; int lu = heap_node[n];
    int i = 0;
    for (;;) {
        int l = 2 * i + 1, rr = l + 1, m = i;
        if (l < hn && heap_key[l] < (m == i ? lk : heap_key[m])) m = l;
        if (rr < hn && heap_key[rr] < (m == i ? lk : heap_key[m])) m = rr;
        if (m == i) break;
        heap_key[i] = heap_key[m]; heap_node[i] = heap_node[m]; i = m;
    }
    heap_key[i] = lk; heap_node[i] = lu;
    return r;
}
static int find(int x) { while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; } return x; }
static char ib[1 << 24], ob[1 << 23];
static char *gp, *op;
static inline int rd() { while (*gp < '0') gp++; int v = 0; while (*gp >= '0' && *gp <= '9') v = v * 10 + (*gp++ - '0'); return v; }
static inline void wr(ll v) {
    if (v < 0) { *op++ = '-'; v = -v; }
    char t[24]; int k = 0;
    if (!v) t[k++] = '0';
    while (v) { t[k++] = (char)('0' + v % 10); v /= 10; }
    while (k) *op++ = t[--k];
    *op++ = '\n';
}
int main() {
    int len = (int)fread(ib, 1, sizeof(ib) - 1, stdin);
    ib[len] = 0; gp = ib; op = ob;
    const ll INF = (ll)4e18;
    int T = rd();
    while (T--) {
        int n = rd(), m = rd();
        for (int i = 1; i <= n; i++) hd[i] = 0;
        ec = 0;
        for (int i = 0; i < m; i++) {
            int u = rd(), v = rd(), l = rd(), a = rd();
            E[i] = Edge{u, v, l, a};
            to[++ec] = v; wt[ec] = l; nx[ec] = hd[u]; hd[u] = ec;
            to[++ec] = u; wt[ec] = l; nx[ec] = hd[v]; hd[v] = ec;
        }
        for (int i = 1; i <= n; i++) dist[i] = INF;
        hn = 0; dist[1] = 0; hpush(1, 0);
        while (hn) {
            ll key; int u = hpop(key);
            if (key > dist[u]) continue;
            for (int e = hd[u]; e; e = nx[e]) {
                int v = to[e]; ll nd = key + wt[e];
                if (nd < dist[v]) { dist[v] = nd; hpush(v, nd); }
            }
        }
        sort(E, E + m, cmpA);
        for (int v = 1; v <= 2 * n; v++) up[0][v] = 0;
        int cnt = n;
        for (int i = 1; i <= n; i++) { fa[i] = i; alt[i] = 1 << 30; }
        for (int i = 0; i < m; i++) {
            int ru = find(E[i].u), rv = find(E[i].v);
            if (ru == rv) continue;
            int nd = ++cnt;
            fa[nd] = nd; alt[nd] = E[i].a;
            lc[nd] = ru; rc[nd] = rv;
            up[0][ru] = nd; up[0][rv] = nd;
            fa[ru] = nd; fa[rv] = nd;
        }
        for (int v = 1; v <= cnt; v++) if (!up[0][v]) up[0][v] = 0;
        for (int k = 1; k < LOG; k++)
            for (int v = 1; v <= cnt; v++) up[k][v] = up[k - 1][up[k - 1][v]];
        for (int v = 1; v <= n; v++) mind[v] = dist[v];
        for (int v = n + 1; v <= cnt; v++) {
            ll a = mind[lc[v]], b = mind[rc[v]];
            mind[v] = a < b ? a : b;
        }
        int Q = rd(), K = rd(), S = rd();
        ll last = 0;
        while (Q--) {
            int v = rd(), p = rd();
            ll kn = (ll)(K % n), ln = last % n;
            v = (int)(((v - 1) + kn * ln) % n + 1);
            ll sp = (ll)(S + 1);
            p = (int)(((ll)p + (ll)(K % sp) * (last % sp)) % sp);
            int x = v;
            for (int k = LOG - 1; k >= 0; k--) {
                int anc = up[k][x];
                if (anc && alt[anc] > p) x = anc;
            }
            last = mind[x];
            wr(last);
        }
    }
    fwrite(ob, 1, op - ob, stdout);
    return 0;
}

评测结果