代码

#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#define Pii pair<int, int>
#define F first
#define S second
#define FI(n) FastIO::read(n)
using namespace std;

namespace FastIO {
  const int SIZE = 1 << 16;
  char buf[SIZE], obuf[SIZE], str[60];
  int bi = SIZE, bn = SIZE, opt;
  int read(char *s) {
    while (bn) {
      for (; bi < bn && buf[bi] <= ' '; bi++);
      if (bi < bn) break;
      bn = fread(buf, 1, SIZE, stdin);
      bi = 0;
    }
    int sn = 0;
    while (bn) {
      for (; bi < bn && buf[bi] > ' '; bi++) s[sn++] = buf[bi];
      if (bi < bn) break;
      bn = fread(buf, 1, SIZE, stdin);
      bi = 0;
    }
    s[sn] = 0;
    return sn;
  }
  bool read(int &x) {
    int n = read(str), bf;
 
    if (!n) return 0;
    int i = 0; if (str[i] == '-') bf = -1, i++; else bf = 1;
    for (x = 0; i < n; i++) x = x * 10 + str[i] - '0';
    if (bf < 0) x = -x;
    return 1;
  }
}

const int N = 201000, M = 401000;

int n, m, tot;
vector<Pii> g[N];
int f[N], b[N];
  
void Dij(void) {
  fill(f + 1, f + n + 1, 2e9);
  f[1] = 0;
  priority_queue<Pii, vector<Pii >, greater<Pii > > pq;
  pq.push(make_pair(0, 1));
  while(!pq.empty()) {
    Pii tmp = pq.top(); pq.pop();
    int u = tmp.S, d = tmp.F;
    if(d != f[u]) continue;
    for(int i = 0; i < g[u].size(); i++) {
      Pii now = g[u][i];
      if(d + now.S < f[now.F]) {
	f[now.F] = d + now.S;
	pq.push(make_pair(f[now.F], now.F));
      }
    }
  }
}

struct Edge {
  int u, v, l, a;
}e[M];

int ls[M * 40], rs[M * 40], siz[M * 40], fa[M * 40], val[M * 40];

bool cmpa(Edge &a, Edge &b) {
  return a.a > b.a;
}

void Build(int &o, int l, int r) {
  o = ++tot;
  if(l == r) {
    fa[o] = l; siz[o] = 1; val[o] = f[l];
    return;
  }
  int mid = l + r >> 1;
  Build(ls[o], l, mid);
  Build(rs[o], mid + 1, r);
}

int Query(int o, int l, int r, int x) {
  if(l == r) return o;
  int mid = l + r >> 1;
  if(x <= mid) return Query(ls[o], l, mid, x);
  else return Query(rs[o], mid + 1, r, x);
}

int Find(int o, int x) {
  int p = Query(o, 1, n, x);
  if(x == fa[p]) return p;
  return Find(o, fa[p]);
}

void Modify(int x, int &y, int l, int r, int u, int v) {
  y = ++tot;
  if(l == r) {
    fa[y] = v;
    siz[y] = siz[x];
    val[y] = val[x];
    return;
  }
  ls[y] = ls[x];
  rs[y] = rs[x];
  int mid = l + r >> 1;
  if(u <= mid) Modify(ls[x], ls[y], l, mid, u, v);
  else Modify(rs[x], rs[y], mid + 1, r, u, v);
}

void Update(int x, int &y, int l, int r, int u, int v) {
  if(x == y) y = ++tot;
  if(l == r) {
    fa[y] = fa[x];
    val[y] = min(val[x], val[v]);
    siz[y] = siz[x] + siz[v];
    return;
  }
  if(!ls[y]) ls[y] = ls[x];
  if(!rs[y]) rs[y] = rs[x];
  int mid = l + r >> 1;
  if(u <= mid) Update(ls[x], ls[y], l, mid, u, v);
  else Update(rs[x], rs[y], mid + 1, r, u, v);
}

int Q, K, S, root[M], ffa[N];

int Ask(int x) {
  return x == ffa[x] ? x : ffa[x] = Ask(ffa[x]);
}

int main(void) {
  freopen("return.in", "r", stdin);
  freopen("return.out", "w", stdout);
  int Ts;
  FI(Ts);
  while(Ts--) {
    FI(n); FI(m);
    for(int i = 1; i <= n; i++)
      g[i].clear(), ffa[i] = i;
    for(int i = 1; i <= m; i++) {
      FI(e[i].u), FI(e[i].v), FI(e[i].l), FI(e[i].a);
      g[e[i].u].push_back(make_pair(e[i].v, e[i].l));
      g[e[i].v].push_back(make_pair(e[i].u, e[i].l));
    }
    FI(Q), FI(K), FI(S);
    sort(e + 1, e + m + 1, cmpa);
    Dij();
    tot = 0;
    Build(root[0], 1, n);
    for(int i = 1; i <= m; i++) {
      root[i] = root[i - 1];
      int x = Query(root[i], 1, n, Ask(e[i].u));
      int y = Query(root[i], 1, n, Ask(e[i].v));
      if(fa[x] != fa[y]) {
	if(siz[x] < siz[y]) swap(x, y);
	ffa[fa[y]] = ffa[fa[x]];
	Modify(root[i - 1], root[i], 1, n, fa[y], fa[x]);
	Update(root[i - 1], root[i], 1, n, fa[x], y);
      }
    }
    //return 0;
    int lst = 0;
    for(int i = 1, v, p; i <= Q; i++) {
      FI(v), FI(p);
      v = (v + K * lst - 1) % n + 1;
      p = (p + K * lst) % (S + 1);
      int l = 1, r = m, ind = 0;
      while(l <= r) {
	int mid = l + r >> 1;
	if(e[mid].a > p) ind = mid, l = mid + 1;
	else r = mid - 1;
      }
      printf("%d\n", lst = val[Find(root[ind], v)]);
    }
    for(int i = 1; i <= tot; i++)
      fa[i] = siz[i] = val[i] = ls[i] = rs[i] = 0;
    //return 0;
  }
}

评测结果