代码

#include <bits/stdc++.h>
#define lowbit(x) (x&-x)
#define loc(x, y) (x-1)*m+y
#define jh(x, y) x^=y^=x^=y
#define rg register
#define inl inline
typedef int ll;
const int N = 2e5 + 5, mod = 1e9 + 7, INF = 0x3f3f3f3f;
using namespace std;
namespace fast_IO {
    inl ll read() {
        rg char c;
        rg ll x = 0;
        rg bool flag = false;
        while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
        if (c == EOF)return c; if (c == '-')flag = true; else x = c ^ 48;
        while ((c = getchar()) != ' ' && c != '\n' && c != '\r'&&~c)
            x = (x << 1) + (x << 3) + (c ^ 48);
        if (flag)return -x; return x;
    }
    inl ll max(rg ll a, rg ll b) { if (a > b)return a; return b; }
    inl ll min(rg ll a, rg ll b) { if (a < b)return a; return b; }
    void write(rg ll x) { if (x < 0)putchar('-'), x = -x; if (x >= 10)write(x / 10); putchar(x % 10 ^ 48); }
}
int n, nt[N << 2], b[N << 2], p[N], num, fa[N << 1][21], f[N], c[N << 1][2], id[N], wa[N << 1];
ll dist[N], w[N << 2], minn[N];
bool flag[N];
struct Node {
    int x, y, z;
    bool operator <(const rg Node &s)const { return z > s.z; }
}e[N << 1];
struct node {
    int id; ll dist;
    node() {}
    node(rg int id, rg ll dist) :id(id), dist(dist) {}
    bool operator <(rg const node &s)const { return dist > s.dist; }
};
priority_queue<node>ppq;
int findf(rg int x) { if (f[x] == x)return x; return f[x] = findf(f[x]); }
inl void add(rg int x, rg int y, rg int z)
{
    b[++num] = y, w[num] = z;
    nt[num] = p[x], p[x] = num;
    b[++num] = x, w[num] = z;
    nt[num] = p[y], p[y] = num;
}
inl void dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    memset(flag, 0, sizeof(flag));
    dist[1] = 0;
    ppq.push(node(1, 0));
    while (!ppq.empty())
    {
        rg node k = ppq.top(); ppq.pop();
        if (flag[k.id])continue;
        flag[k.id] = true;
        for (rg int e = p[k.id]; e; e = nt[e])
        {
            rg int kk = b[e];
            if (dist[kk] - w[e] > dist[k.id])
            {
                dist[kk] = dist[k.id] + w[e];
                if (!flag[kk])ppq.push(node(kk, dist[kk]));
            }
        }
    }
}
void dfs(rg int x)
{
    if (x <= n) { minn[x] = dist[x]; return; }
    dfs(c[x][0]); dfs(c[x][1]);
    minn[x] = fast_IO::min(minn[c[x][0]], minn[c[x][1]]);
}
inl ll query(rg int x, rg int y)
{
    for (rg int j = 20; ~j; --j)
        if (fa[x][j] && wa[fa[x][j]] > y)x = fa[x][j];
    return minn[x];
}

int main(void)
{
    rg int T = fast_IO::read();
    while (T--)
    {
        memset(p, 0, sizeof(p)); num = 0;
        memset(fa, 0, sizeof(fa)); memset(f, 0, sizeof(f));
        memset(c, 0, sizeof(c));
        memset(minn, 0x3f, sizeof(minn));
        n = fast_IO::read(); rg int m = fast_IO::read(), tot = n, cnt = 0;
        for (rg int i = 1; i <= m; ++i)
        {
            rg int u = fast_IO::read(), v = fast_IO::read(),
                l = fast_IO::read(), a = fast_IO::read();
            e[i].x = u, e[i].y = v, e[i].z = a; add(u, v, l);
        }
        dijkstra();
        sort(e + 1, e + m + 1);
        for (rg int i = 1; i <= n; ++i)f[i] = i, id[i] = i;
        for (rg int i = 1; i <= m; ++i)
        {
            rg int fx = findf(e[i].x), fy = findf(e[i].y);
            if (fx == fy)continue;
            f[fx] = fy; fa[id[fy]][0] = fa[id[fx]][0] = ++tot;
            c[tot][0] = id[fx]; c[tot][1] = id[fy];
            id[fy] = tot; wa[tot] = e[i].z;
            if (++cnt == n - 1)break;
        }
        for (rg int j = 1; j <= 20; ++j)
            for (rg int i = 1; i <= tot; ++i)
                fa[i][j] = fa[fa[i][j - 1]][j - 1];
        dfs(tot);
        rg int q = fast_IO::read(), k = fast_IO::read(), s = fast_IO::read();
        rg ll lastans = 0;
        while (q--)
        {
            rg int v = (fast_IO::read() + k * lastans - 1) % n + 1;
            rg int p = (fast_IO::read() + k * lastans) % (s + 1);
            fast_IO::write(lastans = query(v, p)); putchar('\n');
        }
    }
    return 0;
}

评测结果