代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <utility>
#include <functional>
#include <cctype>
const int MAXN = 2e5 + 10;
const int MAXM = 4e5 + 10;

int n, m;
struct Data {
  int u, v, l, a;
}data[MAXM];
struct Edge {
  int v, w, next;
}edge[MAXM << 1];
int head[MAXN], tail;
int q, k, s;
void insert(int u, int v, int w) {
  edge[++tail] = (Edge) {v, w, head[u]}; head[u] = tail;
}
namespace io {
  const int SIZE = 1e6;
  char buff[SIZE];
  char *l = buff, *r = buff;
  void init() {
    l = buff;
    r = l + fread(buff, 1, SIZE, stdin);
  }
  char gc() {
    if (l == r) init();
      return *(l++);
      //return getchar();
  }
  void read(int &x) {
    x = 0;
    char ch = gc();
    while(!isdigit(ch)) ch = gc();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = gc();
  }
}using io::read;
namespace solver1 {
  long long dis[MAXN];
  void dijkstra() {
    memset(dis, 63, sizeof dis);
    
    typedef std::pair<long long, int> Pii;
    
    std::priority_queue <Pii, std::vector<Pii>, std::greater<Pii> > pq;

    dis[1] = 0;
    pq.push(std::make_pair(0, 1));

    while(!pq.empty()) {
      Pii tmp = pq.top(); pq.pop();

      int u = tmp.second;
      long long d = tmp.first;

      if (d != dis[u]) continue;

      for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;

        if (d + edge[i].w < dis[v]) {
          dis[v] = d + edge[i].w;
          pq.push(std::make_pair(dis[v], v));
        }
      }
      
    }
  }

  namespace seg_tree {
    const int SIZE = 1e7;
    struct Node {
      int ls, rs;
      int fa, min, sz, t;
      int to;
    }tree[SIZE];
    int root[MAXM], cnt;
    int newnode() {
      int u = ++cnt;
      memset(tree + u, 0, sizeof tree[u]);
      return u;
    }
    void build(int &node, int l, int r) {
      node = newnode();
      tree[node].ls = tree[node].rs = 0;
      tree[node].t = 0;
      
      if (l == r) {
        tree[node].fa = l;
        tree[node].min = dis[l];
        tree[node].sz = 1;
        return;
      }
      int mid = (l + r) >> 1;

      build(tree[node].ls, l, mid);
      build(tree[node].rs, mid + 1, r);
    }

    void init() {
      memset(root, 0, sizeof root);
      cnt = 0;
      build(root[0], 1, n);
    }

    int p, ve;
    int val, minv, szv;
    void _query(int node, int l, int r) {
      while(1) {
        if (l == r) {
          val = tree[node].fa;
          minv = tree[node].min;
          szv = tree[node].sz;
          return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) {
          node = tree[node].ls, r = mid;
        } else {
          node = tree[node].rs, l = mid + 1;          
        }
        //_query(tree[node].ls, l, mid);
        //else _query(tree[node].rs, mid + 1, r);
      }
    }

    void query(int pos, int ver, int &res, int &min, int &sz) {
      p = pos;
      _query(root[ver], 1, n);
      res = val, min = minv, sz = szv;
      /*
      if (sz > n) {
        fprintf(stderr, "%d %d %d\n", pos, ver, sz);
        throw;
      }
      */
    }

    void _modify(int &cur, int pre, int l, int r) {
      if (tree[cur].t != ve) {
        cur = newnode();
        tree[cur] = tree[pre];
        tree[cur].t = ve;
      }

      if (l == r) {
        tree[cur].fa = val;
        tree[cur].min = minv;
        tree[cur].sz = szv;
        return;
      }

      int mid = (l + r) >> 1;

      if (p <= mid) _modify(tree[cur].ls, tree[pre].ls, l, mid);
      else _modify(tree[cur].rs, tree[pre].rs, mid + 1, r);
    }

    void modify(int pos, int ver, int res, int min, int sz) {
      p = pos;
      val = res;
      minv = min;
      szv = sz;
      ve = ver;
      
      _modify(root[ver], root[ver - 1], 1, n);
    }
    void setroot(int x) {
      root[x] = ++cnt;
      tree[root[x]] = tree[root[x - 1]];
      tree[root[x]].t = x;
    }
    void _print(int node, int l, int r) {
      if (l == r) {
        printf("fa[%d] = %d, ", l, tree[node].fa);
        return;
      }
      int mid = (l + r) >> 1;
      _print(tree[node].ls, l, mid);
      _print(tree[node].rs, mid + 1, r);
    }
    void print() {
      for (int i = 0; i <= m; i++) {
        _print(root[i], 1, n);
        printf("\n");
      }
    }
  }

  int fa[MAXN], min[MAXN], sz[MAXN];
  
  void find(int x, int ver, int &fa, int &min, int &sz) {
    int f, m, s;
    seg_tree::query(x, ver, f, m, s);
    if (f == x) {
      fa = f, min = m, sz = s;
      return;
    }
    find(f, ver, fa, min, sz);
  }

  int find(int x) {
    return x == fa[x] ? x : find(fa[x]);
  }
  bool cmp(const Data &a, const Data &b) {
    return a.a > b.a;
  }
  int val[MAXM];
  void main() {
    
    dijkstra();

    seg_tree::init();

    std::sort(data + 1, data + m + 1, cmp);

    for (int i = 1; i <= n; i++) {
      fa[i] = i; min[i] = dis[i];
      sz[i] = 1;
    }
    
    for (int i = 1; i <= m; i++) {
      int x, minx, szx;
      int y, miny, szy;
      val[i] = data[i].a;
      //find(data[i].u, i - 1, x, minx, szx);
      //find(data[i].v, i - 1, y, miny, szy);
      x = find(data[i].u);
      y = find(data[i].v);
      minx = min[x];
      miny = min[y];
      szx = sz[x];
      szy = sz[y];
      

      if (x == y) {
        seg_tree::setroot(i);
        continue;
      }
      
      if (szx < szy) {
        std::swap(x, y);
        std::swap(minx, miny);
        std::swap(szx, szy);
      }

      seg_tree::modify(y, i, x, miny, szy);
      //fprintf(stderr, "%d %d %d %d %d\n", i, szx, szy, data[i].u, data[i].v);
      seg_tree::modify(x, i, x, std::min(minx, miny), szx + szy);

      min[x] = std::min(minx, miny);
      sz[x] += sz[y];
      fa[y] = fa[x];
      
    }
    
    //seg_tree::print();
    int ans = 0;

    for (int i = 1; i <= q; i++) {
      int v, p;
      //scanf("%d%d", &v, &p);
      read(v); read(p);
      
      //if (i == 12) fprintf(stderr, "%d %d\n", p, k);
      v = (v + (long long) k * ans - 1) % n + 1;
      p = (p + (long long) k * ans) % (s + 1);

      int pos = std::lower_bound(val + 1, val + m + 1, p, std::greater<int>()) - val - 1;
      //if (i == 2) fprintf(stderr, "%d %d %d %d %d %d\n", pos, val[pos - 2], val[pos - 1], val[pos], val[pos + 1], val[pos + 2]);
      
      int x, minx, szx;
      find(v, pos, x, minx, szx);

      ans = minx;
      printf("%d\n", ans);
    }
  }
}

int main() {
#ifndef LOCAL
  //freopen("return.in", "r", stdin);
  //freopen("return.out", "w", stdout);
#endif
  int t;
  //scanf("%d", &t);
  read(t);
  while(t--) {
    memset(head, 0, sizeof head);
    tail = 0;

    //scanf("%d%d", &n, &m);
    read(n); read(m);
    for (int i = 1; i <= m; i++) {
      int u, v, l, a;
      //scanf("%d%d%d%d", &u, &v, &l, &a);
      read(u); read(v); read(l); read(a);
      data[i] = (Data) {u, v, l, a};
      insert(u, v, l);
      insert(v, u, l);
    }

    //scanf("%d%d%d", &q, &k, &s);
    read(q); read(k); read(s);

    solver1::main();
  }
}

评测结果