代码

// This code is AI-generated. (AI 生成的代码)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
// 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>
#include <queue>
#include <vector>
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[2 * MAXN][LOG];
static ll mind[2 * MAXN];
static int find(int x) { while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; } return x; }
static char ib[1 << 26], ob[1 << 26];
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;
        priority_queue<pair<ll,int>, vector<pair<ll,int> >, greater<pair<ll,int> > > pq;
        dist[1] = 0; pq.push(make_pair(0, 1));
        while (!pq.empty()) {
            pair<ll,int> top = pq.top(); pq.pop();
            ll key = top.first; int u = top.second;
            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; pq.push(make_pair(nd, v)); }
            }
        }
        sort(E, E + m, cmpA);
        for (int v = 1; v <= 2 * n; v++) up[v][0] = 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[ru][0] = nd; up[rv][0] = nd;
            fa[ru] = nd; fa[rv] = nd;
        }

        for (int k = 1; k < LOG; k++)
            for (int v = 1; v <= cnt; v++) up[v][k] = up[up[v][k - 1]][k - 1];
        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[x][k];
                if (anc && alt[anc] > p) x = anc;
            }
            last = mind[x];
            wr(last);
        }
    }
    fwrite(ob, 1, op - ob, stdout);
    return 0;
}

评测结果