代码

/*+lmake
 * DEFINE += WAAUTOMATON
 * STD = c++98
 */
#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 lx {
struct Query
{
    int v, p, id;
} qu[MAXQ + 10];
bool comp2(const Query &a, const Query &b)
{
    return a.p > b.p;
}
int fa[MAXN + 10];
LL v[MAXN + 10];
int find(int x)
{
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}
void Union(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy) {
        fa[fy] = fx;
        v[fx] = min(v[fx], v[fy]);
    }
}
void main()
{
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        v[i] = sssp::dis[i];
    }
    sort(e + 1, e + 1 + m, comp);
    for (int i = 1; i <= q; ++i) {
        scanf("%d%d", &qu[i].v, &qu[i].p);
        qu[i].id = i;
    }
    sort(qu + 1, qu + 1 + q, comp2);
    int p = 0;
    for (int i = 1; i <= q; ++i) {
        for (int j = p + 1; j <= m && e[j].h > qu[i].p; ++j) {
            Union(e[j].a, e[j].b);
            p = j;
        }
        ans[qu[i].id] = v[find(qu[i].v)];
    }
}
}
namespace zx {
struct Data
{
    int fa, v, siz;
};
struct Node
{
    Node *lc, *rc;
    Data v;
    Data query(int l, int r, int p);
} node[30 * MAXM + 10];
int c;
Node *copyNode(Node *old, Data v = Data())
{
    Node *now = node + ++c;
    *now = *old;
    now->v = v;
    return now;
}
Data Node::query(int l, int r, int p)
{
    if (l == r)
        return v;
    int mid = (l + r) / 2;
    if (p <= mid)
        return lc->query(l, mid, p);
    return rc->query(mid + 1, r, p);
}
Node *change(Node *o, int l, int r, int p, Data v)
{
    if (l == r)
        return copyNode(o, v);
    int mid = (l + r) / 2;
    Node *now = copyNode(o);
    if (p <= mid)
        now->lc = change(now->lc, l, mid, p, v);
    else
        now->rc = change(now->rc, mid + 1, r, p, v);
    return now;
}
Data find(Node *o, int x)
{
    Data t;
    while ((t = o->query(1, n, x)).fa != x) {
        x = t.fa;
    }
    return t;
}
Node *root[MAXM + 10];
Node *Union(Node *o, int x, int y)
{
    Data fx = find(o, x), fy = find(o, y);
    if (fx.fa == fy.fa)
        return o;
    if (fx.siz > fy.siz) {
		swap(fx,fy);
    }
    o = change(o, 1, n, fy.fa, (Data){ fy.fa, min(fx.v, fy.v), fx.siz + fy.siz });
    return  change(o, 1, n, fx.fa, (Data){ fy.fa, 0, 0 });
}
int tong[MAXM + 10];
void main()
{
	node[0].lc=node[0].rc=node;
    c = 0;
    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);
    root[0] = node;
	for(int i=1; i<=n; ++i) {
		root[0]=change(root[0],1,n,i,(Data){i,static_cast<int>(sssp::dis[i]),1});
	}
    for (int i = 1; i <= m; ++i) {
        root[i] = Union(root[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(root[x],v).v;
		ans[i]=lastans;
    }
}
}
int main()
{
#ifdef WAAUTOMATON
	memset(zx::node,0,sizeof(zx::node));
#endif
    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();
		int t=0;
#ifdef WAAUTOMATON
		t=2;
#endif
        if (k == t)
            lx::main();
		else 
			zx::main();
        for (int i = 1; i <= q; ++i) {
            printf("%lld\n", ans[i]);
        }
    }
}

评测结果