步行的最小距离很容易求，dij随便求一下每个点的最短路，然后找到与 \(v\) 能相互坐车到达的点，对这些点的最短路都有可能是答案，取个 \(\min\) 即可。
所以本题最大的问题是怎么找到在水位线为 \(p\) 时，与 \(v\) 能相互坐车到达的点。可以想到只保留海拔大于 \(p\) 的边，因为只要考虑连通性且对于所有的 \(p\) 都需要考虑，想到 Kruskal 重构树。
在 Kruskal 重构树上用倍增找到深度最浅的海拔大于 \(p\) 的边，这个边对应的点的子树内的点的距离最小值即为答案。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=4e5+10,M=4e5+10,inf=2.1e9,Lg=20;
int n,m,cnt,h[N<<1],dsu[N<<1];
int fa[N][Lg+5],dep[N];
vector<int>G[N<<1];
vector<pii>E[N];
struct edge{
int u,v,w,h;
}e[M];
bool cmp(edge x,edge y){
return x.h>y.h;
}
int getfa(int u){
if(dsu[u]!=u){
dsu[u]=getfa(dsu[u]);
}
return dsu[u];
}
void clear(){
for(int i=1;i<=cnt;i++){
dep[i]=h[i]=0,dsu[i]=i;
vector<int>().swap(G[i]);
vector<pii>().swap(E[i]);
for(int j=0;j<=Lg;j++){
fa[i][j]=0;
}
}
}
int d[N<<1],b[N<<1];
void dij(){
for(int i=1;i<=n;i++){
d[i]=inf;
b[i]=0;
}
d[1]=0;
priority_queue<pii>q;
q.push(mp(0,1));
while(!q.empty()){
int u=q.top().second;
q.pop();
if(b[u]){
continue;
}
b[u]=1;
for(auto x:E[u]){
int v=x.first,w=x.second;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
q.push(mp(-d[v],v));
}
}
}
}
void make_tree(int u){
for(int i=1;i<=Lg;i++){
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(auto v:G[u]){
if(dep[v]){
continue;
}
dep[v]=dep[u]+1;
fa[v][0]=u;
make_tree(v);
d[u]=min(d[u],d[v]);
}
}
int find(int st,int p){
for(int i=Lg;i>=0;i--){
if(h[fa[st][i]]>p){
st=fa[st][i];
}
}
return st;
}
void solve(){
read(n),read(m);
cnt=n;
for(int i=1;i<=m;i++){
read(e[i].u),read(e[i].v),read(e[i].w),read(e[i].h);
}
for(int i=1;i<=n;i++){
h[i]=inf;
dsu[i]=i;
}
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++){
int u=e[i].u,v=e[i].v;
u=getfa(u),v=getfa(v);
if(u!=v){
dsu[v]=dsu[u]=dsu[++cnt]=cnt;
h[cnt]=e[i].h;
G[cnt].pb(u),G[cnt].pb(v);
d[cnt]=inf;
}
}
for(int i=1;i<=m;i++){
E[e[i].u].pb(mp(e[i].v,e[i].w));
E[e[i].v].pb(mp(e[i].u,e[i].w));
}
dij();
dep[cnt]=1;
make_tree(cnt);
int q,opt,s;
read(q),read(opt),read(s);
int lstans=0;
while(q--){
int st,p;
read(st),read(p);
st=(st+opt*lstans-1)%n+1;
p=(p+opt*lstans)%(s+1);
int pos=find(st,p);
lstans=d[pos];
write_endl(lstans);
}
clear();
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}