代码

// NOI2018 归程 (Journey) - Dijkstra + Kruskal reconstruction tree + binary lifting
// Reads stdin straight out of the DuckInfo input buffer (already resident in memory).
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <sys/auxv.h>
using namespace std;
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;

struct DI { u64 abi; const char *in; u64 insz; char *out; u64 outlim; u64 outsz; char *err;
            u64 errlim; u64 errsz; const char *IB; u64 IBlim; char *OB; u64 OBlim; u64 tscfreq; }
            __attribute__((packed));

static unsigned char *IP;
static inline ll rd() {
    unsigned char c = *IP;
    while (c < '0' || c > '9') c = *++IP;
    ll x = 0;
    do { x = x * 10 + (c - '0'); c = *++IP; } while (c >= '0' && c <= '9');
    return x;
}

#define MAXN 200005
#define MAXM 400005
#define LOG 19

static int n, m, tot;
static u32 eu[MAXM], ev[MAXM], el[MAXM], ea[MAXM];
static u32 eord[MAXM], tmp[MAXM];
static u32 deg[MAXN + 1], cstart[MAXN + 2];
static u32 adj_to[2 * MAXM], adj_w[2 * MAXM];
static u32 dst[MAXN + 1];
static u32 dsu[2 * MAXN], tp[2 * MAXN];
static u32 tval[2 * MAXN], tlc[2 * MAXN], trc[2 * MAXN], tmin[2 * MAXN];
static u32 up[LOG][2 * MAXN];
static u64 heap[2 * MAXM + 8];
static int hn;
static u32 lastans;

static inline void hpush(u64 v) {
    int i = hn++;
    while (i) { int p = (i - 1) >> 1; if (heap[p] <= v) break; heap[i] = heap[p]; i = p; }
    heap[i] = v;
}
static inline u64 hpop() {
    u64 top = heap[0], v = heap[--hn];
    int i = 0;
    while (true) {
        int c = 2 * i + 1;
        if (c >= hn) break;
        if (c + 1 < hn && heap[c + 1] < heap[c]) c++;
        if (heap[c] >= v) break;
        heap[i] = heap[c]; i = c;
    }
    if (hn) heap[i] = v;
    return top;
}

static u32 find(u32 x) { while (dsu[x] != x) { dsu[x] = dsu[dsu[x]]; x = dsu[x]; } return x; }

int main() {
    DI *di = (DI *)getauxval(0x6b637564ULL);
    if (di && di->in && di->insz) { IP = (unsigned char *)di->in; }
    else {
        static unsigned char *lbuf = (unsigned char *)malloc(1u << 28);
        size_t r = fread(lbuf, 1, 1u << 28, stdin); (void)r; IP = lbuf;
    }

    ll T = rd();
    // output buffer
    static char *obuf;
    obuf = (char *)malloc(1 << 26);
    size_t olen = 0;

    while (T-- > 0) {
        lastans = 0;
        n = (int)rd(); m = (int)rd();
        for (int i = 0; i < m; i++) {
            eu[i] = (u32)rd(); ev[i] = (u32)rd(); el[i] = (u32)rd(); ea[i] = (u32)rd();
        }
        // ---- CSR adjacency ----
        memset(deg, 0, (n + 2) * sizeof(u32));
        for (int i = 0; i < m; i++) { deg[eu[i]]++; deg[ev[i]]++; }
        u32 s = 0;
        for (int i = 1; i <= n; i++) { cstart[i] = s; s += deg[i]; }
        cstart[n + 1] = s;
        static u32 fill_[MAXN + 1];
        memcpy(fill_, cstart, (n + 2) * sizeof(u32));
        for (int i = 0; i < m; i++) {
            u32 u = eu[i], v = ev[i], w = el[i];
            adj_to[fill_[u]] = v; adj_w[fill_[u]] = w; fill_[u]++;
            adj_to[fill_[v]] = u; adj_w[fill_[v]] = w; fill_[v]++;
        }
        // ---- Dijkstra from 1 ----
        for (int i = 1; i <= n; i++) dst[i] = 0xFFFFFFFFu;
        dst[1] = 0; hn = 0; hpush(0ULL << 18 | 1ULL);
        while (hn) {
            u64 top = hpop();
            u32 d = (u32)(top >> 18), u = (u32)(top & 0x3FFFF);
            if (d > dst[u]) continue;
            for (u32 e = cstart[u]; e < cstart[u + 1]; e++) {
                u32 v = adj_to[e];
                u32 nd = d + adj_w[e];
                if (nd < dst[v]) { dst[v] = nd; hpush(((u64)nd << 18) | v); }
            }
        }
        // ---- Kruskal reconstruction tree (max altitude) ----
        // counting sort edges by altitude descending
        {
            static u32 cnt[65536];
            static u32 eo2[MAXM];
            memset(cnt, 0, sizeof(cnt));
            for (int i = 0; i < m; i++) cnt[ea[i] & 0xFFFF]++;
            u32 acc = 0;
            for (int k = 0; k < 65536; k++) { u32 c = cnt[k]; cnt[k] = acc; acc += c; }
            for (int i = 0; i < m; i++) tmp[cnt[ea[i] & 0xFFFF]++] = i;
            memset(cnt, 0, sizeof(cnt));
            for (int i = 0; i < m; i++) cnt[(ea[tmp[i]] >> 16) & 0xFFFF]++;
            acc = 0;
            for (int k = 0; k < 65536; k++) { u32 c = cnt[k]; cnt[k] = acc; acc += c; }
            for (int i = 0; i < m; i++) eo2[cnt[(ea[tmp[i]] >> 16) & 0xFFFF]++] = tmp[i];
            // eo2 is ascending by altitude; we want descending
            for (int i = 0; i < m; i++) eord[i] = eo2[m - 1 - i];
        }
        for (int i = 1; i <= n; i++) { dsu[i] = (u32)i; tp[i] = 0; tval[i] = 0xFFFFFFFFu; tmin[i] = dst[i]; }
        tot = n;
        for (int i = 0; i < m; i++) {
            u32 id = eord[i];
            u32 a = find(eu[id]), b = find(ev[id]);
            if (a == b) continue;
            int t = ++tot;
            tval[t] = ea[id];
            tlc[t] = a; trc[t] = b;
            tp[a] = (u32)t; tp[b] = (u32)t;
            dsu[a] = (u32)t; dsu[b] = (u32)t; dsu[t] = (u32)t;
            tp[t] = 0;
        }
        for (int t = n + 1; t <= tot; t++) {
            u32 x = tmin[tlc[t]], y = tmin[trc[t]];
            tmin[t] = x < y ? x : y;
        }
        for (int i = 1; i <= tot; i++) up[0][i] = tp[i];
        for (int k = 1; k < LOG; k++) {
            u32 *cur = up[k], *prv = up[k - 1];
            for (int i = 1; i <= tot; i++) { u32 p = prv[i]; cur[i] = p ? prv[p] : 0; }
        }
        // ---- queries ----
        ll Q = rd(), K = rd(), S = rd();
        for (ll q = 0; q < Q; q++) {
            ll v0 = rd(), p0 = rd();
            u32 v, p;
            if (K) {
                v = (u32)((v0 + (ll)K * lastans - 1) % n + 1);
                p = (u32)((p0 + (ll)K * lastans) % (S + 1));
            } else { v = (u32)v0; p = (u32)p0; }
            u32 u = v;
            for (int k = LOG - 1; k >= 0; k--) {
                u32 a = up[k][u];
                if (a && tval[a] > p) u = a;
            }
            u32 ans = tmin[u];
            lastans = ans;
            // itoa
            char tb[12]; int tl = 0;
            if (!ans) tb[tl++] = '0';
            while (ans) { tb[tl++] = (char)('0' + ans % 10); ans /= 10; }
            while (tl) obuf[olen++] = tb[--tl];
            obuf[olen++] = '\n';
            if (olen > (1 << 26) - 32) { fwrite(obuf, 1, olen, stdout); olen = 0; }
        }
    }
    if (olen) fwrite(obuf, 1, olen, stdout);
    return 0;
}

评测结果