代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define sqz main
#define ll long long
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define Rep(i, a, b) for (int i = (a); i < (b); i++)
#define travel(i, u) for (int i = head[u]; ~i; i = edge[i].next)

const ll INF = 2e9, Mo = 998244353;
const int N = 200000, M = 400000;
const double eps = 1e-6;
namespace slow_IO
{
    ll read()
    {
        ll x = 0; int zf = 1; char ch = getchar();
        while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
        if (ch == '-') zf = -1, ch = getchar();
        while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
        return x * zf;
    }
    void write(ll y)
    {
        if (y < 0) putchar('-'), y = -y;
        if (y > 9) write(y / 10);
        putchar(y % 10 + '0');
    }
}
using namespace slow_IO;

int head[N + 5], Dis[N + 5], vis[N + 5];
int edgenum = 0, n, m;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q;
struct node
{
    int vet, val, high, next;
}edge[2 * M + 5];
struct Node
{
    int u, v, l, a;
}E[M + 5];
int cmp(Node X, Node Y)
{
    return X.a > Y.a;
}
void addedge(int u, int v, int l, int a)
{
    edge[edgenum].vet = v;
    edge[edgenum].val = l;
    edge[edgenum].high = a;
    edge[edgenum].next = head[u];
    head[u] = edgenum++;
}

void Dijkstra(int s)
{
    rep(i, 1, n) Dis[i] = INF, vis[i] = 0;
    Q.push(make_pair(0, s)); Dis[s] = 0;
    while (!Q.empty())
    {
        int u = Q.top().second; Q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        travel(i, u)
        {
            int v = edge[i].vet;
            if (!vis[v] && Dis[v] > Dis[u] + edge[i].val)
            {
                Dis[v] = Dis[u] + edge[i].val;
                Q.push(make_pair(Dis[v], v));
            }
        }
    }
}
namespace Subtask1
{
    void Solve()
    {
        int Q = read(), K = read(), S = read(), Lastans = 0;
        while (Q--)
        {
            int v0 = read(), p0 = read();
            v0 = (v0 + K * Lastans - 1) % n + 1;
            p0 = (p0 + K * Lastans) % (S + 1);
            if (p0 >= 1) printf("%d\n", Dis[v0]), Lastans = Dis[v0];
            else puts("0"), Lastans = 0;
        }
    }
}
namespace Subtask2
{
    int Fa[N + 5][21], Min[N + 5][21];
    void dfs(int u, int fa)
    {
        travel(i, u)
        {
            int v = edge[i].vet;
            if (v == fa) continue;
            dfs(v, u);
            Fa[v][0] = u, Min[v][0] = edge[i].high, Dis[v] = Dis[u] + edge[i].val;
        }
    }
    int Find(int x, int y)
    {
        per(i, 20, 0) if (Min[x][i] > y) x = Fa[x][i];
        return x;
    }
    void Solve()
    {
        dfs(1, 0);
        rep(j, 1, 20)
            rep(i, 1, n) Fa[i][j] = Fa[Fa[i][j - 1]][j - 1], Min[i][j] = min(Min[i][j - 1], Min[Fa[i][j - 1]][j - 1]);
        int Q = read(), K = read(), S = read(), Lastans = 0;
        while (Q--)
        {
            int v0 = read(), p0 = read();
            v0 = (v0 + K * Lastans - 1) % n + 1;
            p0 = (p0 + K * Lastans) % (S + 1);
            int x = Find(v0, p0);
            printf("%d\n", Lastans = Dis[x]);
        }
    }
}
namespace Subtask3
{
    int ans;
    int vis[N + 5];
    void dfs(int u, int x)
    {
        vis[u] = 1;
        travel(i, u)
        {
            int v = edge[i].vet;
            if (vis[v] || edge[i].val <= x) continue;
            ans = min(ans, Dis[v]);
            dfs(v, u);
        }
    }
    void Solve()
    {
        int Q = read(), K = read(), S = read(), Lastans = 0;
        while (Q--)
        {
            int v0 = read(), p0 = read();
            rep(i, 1, n) vis[i] = 0;
            v0 = (v0 + K * Lastans - 1) % n + 1;
            p0 = (p0 + K * Lastans) % (S + 1);
            ans = Dis[v0];
            dfs(v0, p0);
            printf("%d\n", Lastans = ans);
        }
    }
}
namespace Subtask4
{
    int X[2 * N + 5], Y[2 * N + 5], head2[2 * N + 5], Fa[2 * N + 5][21], Min[2 * N + 5][21], fa[2 * N + 5], Point[2 * N + 5];
    int edgenum2 = 0, now = 0;
    struct nnode
    {
        int vet, val, next;
    }edge2[4 * N + 5];
    void addedge(int u, int v, int w)
    {
        edge2[edgenum2].vet = v;
        edge2[edgenum2].val = w;
        edge2[edgenum2].next = head2[u];
        head2[u] = edgenum2++;
    }
    struct SegmentTree
    {
        int Left[8 * N + 5], Right[8 * N + 5], Val[8 * N + 5];
        void up(int u)
        {
            Val[u] = min(Val[u + u], Val[u + u + 1]);
        }
        void Build(int u, int l, int r)
        {
            Left[u] = l, Right[u] = r; int mid = (l + r) >> 1;
            if (l == r)
            {
                Val[u] = INF;
                return;
            }
            Build(u + u, l, mid);
            Build(u + u + 1, mid + 1, r);
            up(u);
        }
        void Modify(int u, int pos, int val)
        {
            int l = Left[u], r = Right[u], mid = (l + r) >> 1;
            if (l == r)
            {
                Val[u] = min(Val[u], val);
                return;
            }
            if (pos <= mid) Modify(u + u, pos, val);
            else Modify(u + u + 1, pos, val);
            up(u);
        }
        int Query(int u, int x, int y)
        {
            int l = Left[u], r = Right[u], mid = (l + r) >> 1;
            if (x <= l && y >= r) return Val[u];
            int T = INF;
            if (x <= mid) T = min(T, Query(u + u, x, y));
            if (y > mid) T = min(T, Query(u + u + 1, x, y));
            return T;
        }
    }SGT;
    void dfs(int u, int fa)
    {
        X[u] = ++now;
        Point[now] = u;
        for (int i = head2[u]; ~i; i = edge2[i].next)
        {
            int v = edge2[i].vet;
            if (v == fa) continue;
            Fa[v][0] = u, Min[v][0] = edge2[i].val;
            dfs(v, u);
        }
        Y[u] = now;
    }
    int Find(int x)
    {
        return fa[x] == x ? x : fa[x] = Find(fa[x]);
    }
    void Build()
    {
        rep(i, 1, 2 * n) head2[i] = -1, fa[i] = i;
        edgenum2 = 0; now = 0;
        int cnt = n; sort(E + 1, E + m + 1, cmp);
        rep(i, 1, m)
        {
            int fx = Find(E[i].u), fy = Find(E[i].v);
            if (fx != fy)
            {
                cnt++;
                fa[fx] = fa[fy] = cnt;
                addedge(cnt, fx, E[i].a), addedge(cnt, fy, E[i].a);
                if (cnt == 2 * n - 1) break;
            }
        }
        rep(i, 1, 2 * n)
        rep(j, 0, 20) Min[i][j] = INF;
        rep(i, 1, 20) Fa[Find(1)][i] = Find(1);
        dfs(Find(1), 0);
        SGT.Build(1, 1, 2 * n - 1);
        rep(i, 1, n) SGT.Modify(1, X[i], Dis[i]);
        rep(j, 1, 20)
            rep(i, 1, 2 * n) Fa[i][j] = Fa[Fa[i][j - 1]][j - 1], Min[i][j] = min(Min[i][j - 1], Min[Fa[i][j - 1]][j - 1]);
    }
    void Solve()
    {
        Build();
        int Q = read(), K = read(), S = read(), Lastans = 0;
        while (Q--)
        {
            int v0 = read(), p0 = read();
            v0 = (v0 + K * Lastans - 1) % n + 1;
            p0 = (p0 + K * Lastans) % (S + 1);
            int x = v0;
            per(i, 20, 0) if (Min[x][i] > p0) x = Fa[x][i];
            Lastans = SGT.Query(1, X[x], Y[x]);
            printf("%d\n", Lastans);
        }
    }
}

int sqz()
{
    int T = read();
    while (T--)
    {
        n = read(), m = read();
        rep(i, 1, n) head[i] = -1; edgenum = 0;
        int Flag1 = 1;
        rep(i, 1, m)
        {
            int u = read(), v = read(), l = read(), a = read();
            E[i].u = u, E[i].v = v, E[i].l = l, E[i].a = a;
            addedge(u, v, l, a), addedge(v, u, l, a);
            if (a != 1) Flag1 = 0;
        }
        Dijkstra(1);
        /*if (Flag1) Subtask1::Solve();
        else if (m == n - 1) Subtask2::Solve();
        else if (n <= 1500) Subtask3::Solve();
        else */Subtask4::Solve();
    }
    return 0;
}

评测结果