代码

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

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;
}

const int maxn = 2e5 + 10, maxm = 4e5 + 10;
const int maxlgn = 19;
const li Inf = 1e17;
int n, m, Q, K, S;
li dis[maxn];
vector<int> g[maxn];

struct Edge {
  int u, v, altitude;
  li len;
}e[maxm];

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

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]));
	}
      }
    }
  }
}

namespace Only_One_Altitude {
  void Main(void) {
    Dijk::Solve();
    while (Q--) {
      int v, p;
      read(v), read(p);
      if (p == 0) printf("%d\n", 0);
      else printf("%lld\n", dis[v]);
    }
  }
}

namespace Subtask_Tree {
  int dep[maxn], f[maxn][maxlgn], mn[maxn][maxlgn];

  void Add(int x, int par, int num) {
    dep[x] = dep[par] + 1;
    dis[x] = dis[par] + e[num].len;
    f[x][0] = par;
    mn[x][0] = e[num].altitude;
    for (int i = 1; i < maxlgn; ++i) {
      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]);
    }
  }
  
  void Dfs(int x) {
    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 (y == f[x][0]) continue;
      Add(y, x, num);
      Dfs(y);
    }
  }
  
  void Main(void) {
    dep[1] = 1;
    dis[1] = 0LL;
    Dfs(1);
    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];
      }
      printf("%lld\n", dis[v]);
      lastans = dis[v];
    }
  }
}

namespace Brute {
  bool vis[maxn];
  
  queue<int>q;
  li Solve(int v, int p) {
    li ans = Inf;
    memset(vis, 0, sizeof vis);
    vis[v] = 1;
    q.push(v);
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      Min(ans, dis[x]);
      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] || e[num].altitude <= p) continue;
	q.push(y);
	vis[y] = 1;
      }
    }
    return ans;
  }
  
  void Main(void) {
    Dijk::Solve();
    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);
      lastans = Solve(v, p);
      printf("%lld\n", lastans);
    }
  }
}

namespace Off_Line {
  int fa[maxn];
  li answer[maxm];
  
  struct que {
    int v, p, id;
    inline bool operator < (const que &oth) const {
      return p > oth.p;
    }
  }querys[maxm];
  
  inline bool ecmp(Edge x, Edge y) {
    return x.altitude > y.altitude;
  }

  int Find(int x) {
    if (fa[x] != x) fa[x] = Find(fa[x]);
    return fa[x];
  }
  void Unite(int x, int y) {
    int fx = Find(x), fy = Find(y);
    if (fx != fy) {
      fa[fx] = fy;
      li tmp = min(dis[fx], dis[fy]);
      dis[fx] = dis[fy] = tmp;
    }
  }
  
  void Main(void) {
    Dijk::Solve();
    sort(e + 1, e + 1 + m, ecmp);
    for (int i = 1; i <= Q; ++i)
      read(querys[i].v), read(querys[i].p);
    for (int i = 1; i <= Q; ++i)
      querys[i].id = i;
    sort(querys + 1, querys + 1 + Q);

    for (int i = 1; i <= n; ++i)
      fa[i] = i;

    int pos = 1;
    for (int t = 1; t <= Q; ++t) {
      while (pos <= m && e[pos].altitude > querys[t].p) {
	Unite(e[pos].u, e[pos].v);
	++pos;
      }
      int fa = Find(querys[t].v);
      answer[querys[t].id] = dis[fa];
    }

    for (int i = 1; i <= Q; ++i)
      printf("%lld\n", answer[i]);
  }
}

int main(void) { 
  int cas;
  read(cas);
  while (cas--) {
    read(n), read(m);
    InitMemory();
    
    bool sub_flag = 1;
    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);
      if (al != 1) sub_flag = 0;
    }
    
    read(Q), read(K), read(S);
    if (sub_flag) {
      Only_One_Altitude::Main();
      continue;
    }
    if (m == n - 1) {
      Subtask_Tree::Main();
      continue;
    }
    if (K == 0) {
      Off_Line::Main();
      continue;
    }
    Brute::Main();
  }

  return 0;
}

评测结果