代码

// Problem: P4768 [NOI2018] 归程
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4768
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// Author: Moyou
// Copyright (c) 2022 Moyou All rights reserved.
// Date: 2023-01-02 00:16:28

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;

const int N = 2e5 + 10, M = 8e5 + 10;

int lastans, n, m, Q, K, mp;       // mp对应题目中S
int pcnt,                          // 虚点数量
    pval[(N << 1)],                // 虚点的值（海拔）
    low[(N << 1)];                 // 虚点的所有子节点中到1的最小距离
int h[(N << 1)], ne[M], e[M], idx; // 链式前向星存储Kruskal重构树
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

vector<PII> g[N]; // vector存储用于跑最短路的图

struct qwq // 一条边
{
    int u, v, d, al;
};

int read()
{
    int x = 0, f = 1;
    char ch;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return f * x;
}

int fa[(N << 1)];
qwq edge[M];
void init()
{
    lastans = 0;
    n = read(), m = read();
    memset(h, -1, sizeof h);
    memset(low, 0x3f, sizeof low);
    idx = 0;
    pcnt = n;
    for (int i = 1; i <= (n << 1); i++)
        g[i].clear();
    for (int i = 1; i <= m; i++)
    {
        int a = read(), b = read(), c = read(), d = read();
        edge[i] = {a, b, c, d};
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    Q = read(), K = read(), mp = read();
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}

int dist[N];
bool st[N];
void dijkstra(int s)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, s});
    dist[s] = 0;
    while (heap.size())
    {
        auto t = heap.top().y;
        heap.pop();
        if (st[t])
            continue;
        st[t] = 1;
        for (auto i : g[t])
        {
            int j = i.x, w = i.y;
            if (dist[j] > dist[t] + w)
            {
                dist[j] = dist[t] + w;
                heap.push({dist[j], j});
            }
        }
    }
    for (int i = 1; i <= n; i++)
        low[i] = dist[i];
}

int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void kruskal()
{
    sort(edge + 1, edge + m + 1, [](qwq a, qwq b) { return a.al > b.al; });
    for (int i = 1; i <= m; i++)
    {
        int x = find(edge[i].u), y = find(edge[i].v);
        if (x == y)
            continue;
        fa[x] = fa[y] = fa[++pcnt] = pcnt;
        pval[pcnt] = edge[i].al;
        add(pcnt, x), add(pcnt, y);
    }
}

int f[(N << 1)][23];
void lcadfs(int p, int pa)
{
    f[p][0] = pa;
    for (int i = 1; i <= 20; i++)
        f[p][i] = f[f[p][i - 1]][i - 1];
    for (int i = h[p]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == pa) continue;
        lcadfs(j, p);
        low[p] = min(low[p], low[j]);
    }
}

int get_ans(int v, int p)
{
    for (int i = 20; i >= 0; i--)
        if (f[v][i] && pval[f[v][i]] > p)
            v = f[v][i];

    return low[v];
}

void output()
{
    while (Q--)
    {
        int v0 = read(), p0 = read();
        v0 = (v0 + K * lastans - 1) % n + 1;
        p0 = (p0 + K * lastans) % (mp + 1);

        printf("%d\n", lastans = get_ans(v0, p0));
    }
}

void work()
{
    init();
    dijkstra(1);
    kruskal();
    lcadfs(pcnt, 0);
    output();
}

int main()
{
    int T = read();
    while (T--)
    {
        work();
    }
    cout << endl;
    return 0;
}

评测结果