代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstring>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> P;
typedef long long LL;
const int N = 2e5 + 10, M = 8e5 + 10, INF = 0x3f3f3f3f;

struct node
{
    int u, v, l, a;
} e[M], Q[N >> 1];

int ans[N], fa[N], Dis[N], dis[N], fst[N], wei[M], nxt[M],
    to[M], E = 1, vis[N], level[M];

int getfa(int rt)
{
    return fa[rt] == rt ? rt : fa[rt] = getfa(fa[rt]);
}

void add(int u, int v, int w, int l)
{
    to[++E] = v, nxt[E] = fst[u], fst[u] = E, wei[E] = w, level[E] = l;
}

bool cmp(node x, node y)
{
    return x.a > y.a;
}

priority_queue<P, vector<P>, greater<P> > h;
void Dij(int s)
{
    memset(dis, INF, sizeof dis);
    h.push(P(0, s));
    while (!h.empty())
    {
        P tmp = h.top(); h.pop();
        int u = tmp.se;
        if (vis[u]) continue;
        vis[u] = 1, dis[u] = tmp.fi;
        for (int i = fst[u]; i != -1; i = nxt[i]) if (!vis[to[i]])
        {
            h.push(P(dis[u] + wei[i], to[i]));
        }
    }
}

int dfs(int rt, int x)
{
    int ret = dis[rt];
    vis[rt] = 1;
    for (int i = fst[rt]; i != -1; i = nxt[i]) if (!vis[to[i]] && level[i] > x)
    {
        ret = min(dfs(to[i], x), ret);
    }
    return ret;
}

int main()
{
    int n, m, q, k, s, T;
    scanf("%d", &T);
    while (T--)
    {
        memset(fst, -1, sizeof fst);
        memset(vis, 0, sizeof vis); E = 0;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d%d%d", &e[i].u, &e[i].v, &e[i].l, &e[i].a);
            add(e[i].u, e[i].v, e[i].l, e[i].a);
            add(e[i].v, e[i].u, e[i].l, e[i].a);
        }
        Dij(1);
        scanf("%d%d%d", &q, &k, &s);
        if (k == 0)
        {
            sort(e + 1, e + m + 1, cmp);
            for (int i = 1; i <= n; i++) fa[i] = i, Dis[fa[i]] = dis[i];
            int pos = 1;
            for (; pos <= m  && e[pos].a > s; pos++)
            {
                int fv = getfa(e[pos].v), fu = getfa(e[pos].u);
                Dis[fv] = min(Dis[fv], Dis[fu]);
                fa[fu] = fv;
            }
            for (int i = 1; i <= q; i++)
                scanf("%d%d", &Q[i].u, &Q[i].a), Q[i].l = i;
            sort(Q + 1, Q + q + 1, cmp);
            for (int i = 1; i <= q; i++)
            {
                s = Q[i].a;
                for (; pos <= m && e[pos].a > s; pos++)
                {
                    int fv = getfa(e[pos].v), fu = getfa(e[pos].u);
                    Dis[fv] = min(Dis[fv], Dis[fu]);
                    fa[fu] = fv;
                }
                // for (int j = 1; j <= n; j++) printf("%d ", getfa(j));
                // puts("");
                ans[Q[i].l] = Dis[getfa(Q[i].u)];
                // printf("%d\n", pos);
            }
            for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
        }
        else
        {
            int b, x, las = 0;
            if (n <= 1500 && m <= 4000 && q <= 2000)
            {
                for (int i = 1; i <= q; i++)
                {
                    memset(vis, 0, sizeof vis);
                    scanf("%d%d", &b, &x);
                    b = (b + las - 1) % n + 1;
                    x = (x + las) % (s + 1);
                    printf("%d\n", las = dfs(b, x));
                }
            }
            else puts("Not Yet!");
        }
    }
    return 0;
}

评测结果