代码

/*+lmake
 * DEFINE += WAAUTOMATON
 */
#include <cstdio>
#include <algorithm>
#include <queue>
#include <climits>
#include <cstring>
#ifdef WAAUTOMATON
#define debug(args...)                                                                             \
    {                                                                                              \
        dbg, args;                                                                                 \
        cerr << endl;                                                                              \
    }
#define massert(x) assert(x)
#else
#define debug(args...) // Just strip off all debug tokens
#define massert(x)
#endif
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAXN 200000
#define MAXM 400000
#define MAXQ 400000
#define INF (LLONG_MAX / 10)
typedef pair<int, int> pii;
namespace sssp {
struct Edge
{
    int to, next, dis;
} e[2 * MAXM + 10];
int c;
int head[MAXN + 10];
void addEdge(int a, int b, int dis)
{
    e[++c] = (Edge){ b, head[a], dis };
    head[a] = c;
    e[++c] = (Edge){ a, head[b], dis };
    head[b] = c;
}
LL dis[MAXN + 10];
typedef pair<LL, int> pli;
void dijkstra(int s = 1)
{
    fill(dis, dis + MAXN + 1, INF);
    priority_queue<pli, vector<pli>, greater<pli>> q;
    dis[s] = 0;
    q.push(pli(0, s));
    while (!q.empty()) {
        pli tt = q.top();
        q.pop();
        int now = tt.second;
        if (dis[now] != tt.first)
            continue;
        for (int i = head[now]; i != 0; i = e[i].next) {
            int v = e[i].to;
            if (dis[now] + e[i].dis < dis[v]) {
                dis[v] = dis[now] + e[i].dis;
                q.push(pli(dis[v], v));
            }
        }
    }
}
}
LL ans[MAXQ + 10];
struct E
{
    int a, b, l, h;
} e[MAXM + 10];
bool comp(const E &a, const E &b)
{
    return a.h > b.h;
}
int n, m, q, k, s;
namespace zx {
struct Data
{
    int time,fa, v, siz;
};
bool comp3(const Data& a,const Data& b)
{
	return a.time<b.time;
}
vector<Data> x[MAXN+10];
Data query(int time,int p)
{
	return *(upper_bound(x[p].begin(),x[p].end(),(Data){time,0,0,0},comp3)-1);
}
void change(int p,const Data& v)
{
	x[p].push_back(v);
}
Data find(int time, int x)
{
    Data t;
    while ((t = query(time,x)).fa != x) {
        x = t.fa;
    }
    return t;
}
void Union(int time, int x, int y)
{
    Data fx = find(time, x), fy = find(time, y);
    if (fx.fa == fy.fa)
        return ;
    if (fx.siz > fy.siz) {
        swap(fx, fy);
    }
    change(fy.fa, (Data){time+1, fy.fa, min(fx.v, fy.v), fx.siz + fy.siz });
    return change(fx.fa, (Data){time+1, fy.fa, 0, 0 });
}
int tong[MAXM + 10];
void main()
{
    for (int i = 1; i <= m; ++i) {
        tong[i] = e[i].h;
    }
    tong[m + 1] = s + 10;
    sort(tong + 1, tong + 1 + m);
    sort(e + 1, e + 1 + m, comp);
	for(int i=1; i<=n; ++i) {
		x[i].clear();
	}
    for (int i = 1; i <= n; ++i) {
        change(i, (Data){0, i, static_cast<int>(sssp::dis[i]), 1 });
    }
    for (int i = 1; i <= m; ++i) {
        Union(i-1, e[i].a, e[i].b);
    }
    int lastans = 0;
    for (int i = 1; i <= q; ++i) {
        int v, p;
        scanf("%d%d", &v, &p);
        v = (v + k * lastans - 1) % n + 1;
        p = (p + k * lastans) % (s + 1);
        int x = upper_bound(tong + 1, tong + 1 + m + 1, p) - tong;
        x = m - x + 1;
        lastans = find(x, v).v;
        ans[i] = lastans;
    }
}
}
int main()
{
    freopen("return.in", "r", stdin);
#ifndef WAAUTOMATON
    freopen("return.out", "w", stdout);
#endif
    int T;
    scanf("%d", &T);
    while (T--) {
        sssp::c = 0;
        memset(sssp::head, 0, sizeof(sssp::head));
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d%d%d", &e[i].a, &e[i].b, &e[i].l, &e[i].h);
            sssp::addEdge(e[i].a, e[i].b, e[i].l);
        }
        scanf("%d%d%d", &q, &k, &s);
        sssp::dijkstra();
        zx::main();
        for (int i = 1; i <= q; ++i) {
            printf("%lld\n", ans[i]);
        }
    }
}

评测结果