代码

// This code is AI-generated. (AI 生成的代码)
// NOI2018 归程.
//   - Dijkstra from 1 with 32-bit distances and a lazy packed (dist<<32|node)
//     binary heap; l <= 1e4 so every shortest distance fits in u32.
//   - Edges are sorted by altitude with a stable 16-bit LSD radix sort.
//   - Kruskal reconstruction tree with union by size; the subtree minimum
//     walking distance is computed while the tree is built.
//   - Binary lifting answers each query; K == 0 avoids all modulo arithmetic.
//   - All I/O goes straight through the DuckInfo buffers.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include <sys/auxv.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>

typedef unsigned int u32;
typedef unsigned long long u64;

enum { MAXN = 200005, MAXM = 400005, MAXV = 400010, LOG = 18 };

struct DuckInfo {
    u64 abi_version;
    const char *stdin_ptr; u64 stdin_size;
    char *stdout_ptr; u64 stdout_limit; u64 stdout_size;
    char *stderr_ptr; u64 stderr_limit; u64 stderr_size;
    const char *IB_ptr; u64 IB_limit;
    char *OB_ptr; u64 OB_limit;
    u64 tsc_frequency;
} __attribute__((packed));

static const char *ip;
static char *op;
static char local_ib[1 << 26], local_ob[1 << 26];

static inline u32 rd() {
    const char *p = ip;
    while ((unsigned)(*p - '0') > 9u) p++;
    u32 x = 0;
    do { x = x * 10u + (u32)(*p++ - '0'); } while ((unsigned)(*p - '0') <= 9u);
    ip = p;
    return x;
}
static inline void put_u32(u32 x) {
    char *o = op, buf[16];
    int n = 0;
    do { buf[n++] = (char)('0' + x % 10); x /= 10; } while (x);
    while (n) *o++ = buf[--n];
    *o++ = '\n';
    op = o;
}

static int head[MAXN], to[2 * MAXM], nxt[2 * MAXM];
static u32 wt[2 * MAXM];
static int eu[MAXM], ev[MAXM];
static u32 el[MAXM], ea[MAXM];
static int order[MAXM], tmp[MAXM];
static u32 dist[MAXN];
static u64 heap[2 * MAXM + 4];
static int hn;
static int dsu[MAXN], sz[MAXN], rep[MAXN];
static u32 val[MAXV], mn[MAXV];
static int up[MAXV][LOG];

static inline void hpush(u64 v) {
    int i = ++hn;
    while (i > 1) {
        int p = i >> 1;
        if (heap[p] <= v) break;
        heap[i] = heap[p]; i = p;
    }
    heap[i] = v;
}
static inline u64 hpop() {
    u64 top = heap[1], last = heap[hn--];
    int i = 1;
    for (;;) {
        int l = i << 1;
        if (l > hn) break;
        int r = l + 1;
        int c = (r <= hn && heap[r] < heap[l]) ? r : l;
        if (last <= heap[c]) break;
        heap[i] = heap[c]; i = c;
    }
    heap[i] = last;
    return top;
}
static inline int find(int x) {
    int r = x;
    while (dsu[r] != r) r = dsu[r];
    while (dsu[x] != x) { int t = dsu[x]; dsu[x] = r; x = t; }
    return r;
}

int main() {
    struct DuckInfo *d = (struct DuckInfo *)getauxval(0x6b637564UL);
    if (d) { ip = d->stdin_ptr; op = d->stdout_ptr; }
    else {
        size_t z = fread(local_ib, 1, sizeof(local_ib) - 1, stdin);
        local_ib[z] = 0; ip = local_ib; op = local_ob;
    }

    static u32 cnt[65536];
    int T = rd();
    while (T--) {
        int n = rd(), m = rd();
        for (int i = 0; i < m; i++) {
            eu[i] = rd(); ev[i] = rd(); el[i] = rd(); ea[i] = rd();
            order[i] = i;
        }
        for (int i = 1; i <= n; i++) head[i] = 0;
        int ec = 0;
        for (int i = 0; i < m; i++) {
            int u = eu[i], v = ev[i];
            u32 l = el[i];
            to[++ec] = v; wt[ec] = l; nxt[ec] = head[u]; head[u] = ec;
            to[++ec] = u; wt[ec] = l; nxt[ec] = head[v]; head[v] = ec;
        }

        for (int i = 1; i <= n; i++) dist[i] = 0xffffffffu;
        dist[1] = 0; hn = 0; hpush(1);
        while (hn) {
            u64 key = hpop();
            int u = (int)(key & 0xffffffffu);
            u32 dd = (u32)(key >> 32);
            if (dd != dist[u]) continue;
            for (int e = head[u]; e; e = nxt[e]) {
                int v = to[e];
                u32 nd = dd + wt[e];
                if (nd < dist[v]) { dist[v] = nd; hpush(((u64)nd << 32) | (u32)v); }
            }
        }

        // stable LSD radix sort of edge indices by altitude (2 x 16 bits)
        {
            int *src = order, *dst = tmp;
            for (int shift = 0; shift < 32; shift += 16) {
                memset(cnt, 0, sizeof(cnt));
                for (int i = 0; i < m; i++) cnt[(ea[src[i]] >> shift) & 0xffffu]++;
                u32 sum = 0;
                for (int c = 0; c < 65536; c++) { u32 t = cnt[c]; cnt[c] = sum; sum += t; }
                for (int i = 0; i < m; i++)
                    dst[cnt[(ea[src[i]] >> shift) & 0xffffu]++] = src[i];
                int *sw = src; src = dst; dst = sw;
            }
            // two passes leave src == order
        }

        for (int i = 1; i <= n; i++) {
            dsu[i] = i; sz[i] = 1; rep[i] = i;
            mn[i] = dist[i]; up[i][0] = 0;
        }
        int tot = n;
        for (int idx = m - 1; idx >= 0; idx--) {
            int e = order[idx];
            int ru = find(eu[e]), rv = find(ev[e]);
            if (ru == rv) continue;
            ++tot;
            val[tot] = ea[e];
            int t1 = rep[ru], t2 = rep[rv];
            up[t1][0] = tot; up[t2][0] = tot;
            u32 m1 = mn[t1], m2 = mn[t2];
            mn[tot] = m1 < m2 ? m1 : m2;
            if (sz[ru] < sz[rv]) { int t = ru; ru = rv; rv = t; }
            dsu[rv] = ru; sz[ru] += sz[rv]; rep[ru] = tot;
        }
        up[tot][0] = 0;

        for (int j = 1; j < LOG; j++)
            for (int i = 1; i <= tot; i++)
                up[i][j] = up[up[i][j - 1]][j - 1];

        int Q = rd(), K = rd();
        u32 S = rd();
        if (K == 0) {
            for (int q = 0; q < Q; q++) {
                int v = rd(); u32 p = rd();
                int cur = v;
                for (int j = LOG - 1; j >= 0; j--) {
                    int anc = up[cur][j];
                    if (val[anc] > p) cur = anc;
                }
                put_u32(mn[cur]);
            }
        } else {
            u32 lastans = 0, sp1 = S + 1;
            for (int q = 0; q < Q; q++) {
                u32 v0 = rd(), p0 = rd();
                int v = (int)((v0 + lastans - 1u) % (u32)n) + 1;
                u32 p = (p0 + lastans) % sp1;
                int cur = v;
                for (int j = LOG - 1; j >= 0; j--) {
                    int anc = up[cur][j];
                    if (val[anc] > p) cur = anc;
                }
                lastans = mn[cur];
                put_u32(lastans);
            }
        }
    }
    if (!d) { fwrite(local_ob, 1, op - local_ob, stdout); return 0; }
    d->stdout_size = (u64)(op - d->stdout_ptr);
    __asm__ volatile("mov $60, %%rax; xor %%rdi, %%rdi; syscall" ::: "rax", "rdi", "memory");
    __builtin_unreachable();
}

评测结果