代码

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define mp make_pair
#define pb push_back
using namespace std;

namespace Header_Template {
  typedef long long li;
  template<class T>inline void read(T &x) {
    x = 0;
    T tmp = 1;
    char c = getchar();
    while ((c < '0' || c > '9') && c != '-') c = getchar();
    if (c == '-') tmp = -1, c = getchar();
    while (c >= '0' && c <= '9')
      x = (x << 1) + (x << 3) + c - '0', c = getchar();
    x *= tmp;
  }
  template<class T>inline void Max(T &x, T y) {
    if (y > x) x = y;
  }
  template<class T>inline void Min(T &x, T y) {
    if (y < x) x = y;
  }
}
using namespace Header_Template;

const int maxn = 2e5 + 10, maxm = 4e5 + 10;
const int maxlgn = 20;
const int inf = 1e9;
const li Inf = 1e17;
int n, m, Q, K, S;
int val[maxn << 1];
int par[maxn << 1], fa[maxn << 1];
int f[maxn << 1][maxlgn], mn[maxn << 1][maxlgn];
li dis[maxn << 1];
vector<int> g[maxn << 1];
vector<int> tree_edge;

void InitMemory(int n0) {
  for (int i = 1; i <= n0; ++i)
    g[i].clear();
}

struct Edge {
  int u, v, altitude;
  li len;
  inline bool operator < (const Edge &p) const {
    return altitude > p.altitude;
  }
}e[maxm];

namespace Dijk {
  bool vis[maxn];
  struct node {
    int x;
    li dist;
    node() {}
    node(int _x, li _dist) : x(_x), dist(_dist) {}
    inline bool operator < (const node &p) const {
      return dist > p.dist;
    }
  };
  
  priority_queue<node> q;
  
  void Solve(void) {
    memset(vis, 0, sizeof vis);
    fill(dis + 1, dis + 1 + n, Inf);
    dis[1] = 0LL;
    q.push(node(1, 0LL));
    while (!q.empty()) {
      node now = q.top();
      q.pop();
      for (; !q.empty() && vis[now.x];
	   now = q.top(), q.pop());
      if (vis[now.x]) break;
      int x = now.x;
      vis[x] = 1;
      for (int i = 0; i < (int)g[x].size(); ++i) {
	int num = g[x][i];
	int y = (e[num].u == x) ? e[num].v : e[num].u;
	if (!vis[y] && dis[y] > dis[x] + e[num].len) {
	  dis[y] = dis[x] + e[num].len;
	  q.push(node(y, dis[y]));
	}
      }
    }
  }
}

int Find(int x) {
  if (fa[x] != x) fa[x] = Find(fa[x]);
  return fa[x];
}
bool Unite(int x, int y) {
  int fx = Find(x), fy = Find(y);
  if (fx != fy) {
    fa[fx] = fy;
    return 1;
  }
  return 0;
}

int id;
inline int Newnode(int al) {
  ++id;
  val[id] = al;
  return id;
}
void Build(void) {
  InitMemory(n << 1);
  for (int i = 1; i < (n << 1); ++i)
    fa[i] = i;
  id = n;
  fill(val + 1, val + 1 + n, inf);
  memset(par, 0, sizeof par);
  for (int t = 0; t < (int)tree_edge.size(); ++t) {
    int num = tree_edge[t];
    int x = Find(e[num].u), y = Find(e[num].v);
    int u = Newnode(e[num].altitude);
    par[x] = par[y] = u;
    fa[x] = fa[y] = u;
    dis[u] = min(dis[x], dis[y]);
  }

  for (int i = 1; i < (n << 1); ++i) {
    f[i][0] = par[i];
    mn[i][0] = min(val[i], val[par[i]]);
  }
  for (int i = 1; i < maxlgn; ++i)
    for (int x = 1; x < (n << 1); ++x) {
      f[x][i] = f[f[x][i - 1]][i - 1];
      mn[x][i] = min(mn[x][i - 1], mn[f[x][i - 1]][i - 1]);
    }
}

int main(void) {
  int cas;
  read(cas);
  while (cas--) {
    read(n), read(m);
    InitMemory(n);
    
    for (int i = 1, x, y, len, al; i <= m; ++i) {
      read(x), read(y), read(len), read(al);
      e[i].u = x, e[i].v = y;
      e[i].len = (li)len, e[i].altitude = al;
      g[x].pb(i);
      g[y].pb(i);
    }
    Dijk::Solve();

    sort(e + 1, e + 1 + m);
    for (int i = 1; i <= n; ++i)
      fa[i] = i;
    tree_edge.clear();
    for (int i = 1; i <= m; ++i)
      if (Unite(e[i].u, e[i].v))
	tree_edge.pb(i);
    Build();
    
    read(Q), read(K), read(S);
    li lastans = 0;
    int v0, p0, v, p;
    while (Q--) {
      read(v0), read(p0);
      v = (v0 + lastans * K - 1) % n + 1;
      p = (p0 + lastans * K) % (S + 1);
      while (mn[v][0] > p) {
	for (int i = maxlgn - 1; i >= 0; --i)
	  if (mn[v][i] > p) v = f[v][i];
      }
      lastans = dis[v];
      printf("%lld\n", lastans);
    }
  }

  return 0;
}

评测结果