代码

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = gch()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = gch();
    if(b == 1)
        x *= -1;
}

int n, t, la, lb, lc, ld, m, tot, head[200020], fa[200020][25], v[200020][25];

int ans, q, k, s, dis[200020], f[200020], de[200020];

struct in
{
    int to, ne, co;
}ter[800080], es[400040];

struct ex
{
    int pos, dis;
    inline bool operator < (const ex &a) const
    {
        return dis > a.dis;
    }
};

priority_queue <ex> qwq;

bool flag[200020];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], c}, head[l] = tot;
}

inline void dij()
{
    memset(dis, 63, sizeof(dis)), memset(flag, 0, sizeof(flag)), dis[1] = 0;
    while(!qwq.empty())
        qwq.pop();
    qwq.push((ex){1, 0});
    while(!qwq.empty())
    {
        ex qaq = qwq.top(); qwq.pop();
        if(flag[qaq.pos] == 1)
            continue;
        flag[qaq.pos] = 1;
        for(ri i = head[qaq.pos]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(dis[to] > qaq.dis + ter[i].co)
            {
                dis[to] = qaq.dis + ter[i].co;
                if(flag[to] == 0)
                    qwq.push((ex){to, dis[to]});
            }
        } 
    }
}

inline bool cmp(in a, in b)
{
    return a.co > b.co;
}

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

int main()
{
    re(t);
    while(t --)
    {
        re(n), re(m); memset(head, -1, sizeof(head)), tot = -1;
        for(ri i = 1; i <= m; i ++)
            re(la), re(lb), re(lc), re(ld), build(la, lb, lc), es[i] = (in){la, lb, ld};
        dij(), ans = 0; 
        sort(es + 1, es + 1 + m, cmp), memset(de, 0, sizeof(de)), memset(v, 63, sizeof(v));
        for(ri i = 1; i <= n; i ++)
            f[i] = i;
        for(ri i = 1; i <= m; i ++)
        {
            int fx = find(es[i].to), fy = find(es[i].ne);
            if(fx != fy)
            {
                if(dis[fx] > dis[fy])
                    swap(fx, fy);
                f[fy] = fx, fa[fy][0] = fx, v[fy][0] = es[i].co;
            }
        }
        for(ri i = 1; i <= log2(n); i ++)
            for(ri j = 1; j <= n; j ++)
                fa[j][i] = fa[fa[j][i - 1]][i - 1], v[j][i] = min(v[j][i - 1], v[fa[j][i - 1]][i - 1]);
        re(q), re(k), re(s);
        while(q --)
        {
            re(la), re(lb);
            la = (la + k * ans - 1) % n + 1;
            lb = (lb + k * ans) % (s + 1);
            for(ri i = log2(n); i >= 0; i --)
                if(fa[la][i] != 0 && v[la][i] > lb)
                    la = fa[la][i];
            ans = dis[la], printf("%d\n", ans);
        }
    }	
} 

评测结果