题目大意：给定一张$n$个点$m$条边的无向图。每条边有长度和海拔。有$Q$次询问，每次给定起点$v$和当天水位线$p$，每次终点都是$1$。人可以选择坐车或走路，车只能在海拔大于水位线的路上跑。问人步行的最小距离。
----------------------------------
我们可以转化一下题意：在$v$到$1$的路径上寻找断点$u$，使得从$v$到$u$的路径上车都可以跑，且从$u$到$1$步行的路径是满足前置条件的最短的一条路。
显然从$v$开车出发可以到达的点路径的海拔都是大于水位线的。
于是我们可以用$kruskal$重构树求解。（虽然我也不知道为什么用重构树，但是学姐讲课就是这么讲的
我们将边以海拔作为关键字降序排序，构建一颗形如小根堆的$kruskal$重构树。对于每次询问我们找出树上深度最浅且海拔大于$p$的结点，由$kruskal$重构树的性质可知，它子树的所有结点都可由$v$开车到达。求解这个结点可以倍增解决，两行搞定。
对于最短路，因为是无向边，我们可以预处理$1$的单源最短路径。然后对重构树进行$dfs$便可求出子树内的最短路。
PS:关于$spfa$，它死了。
时间复杂度$O(T(q\log n+n))$
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=;
int n,m,Q,T,K,S,val[maxn],tot,minn[maxn],f[maxn],fa[maxn][],last;
int head[maxn],cnt,dis[maxn],vis[maxn];
struct edge{int next,to,dis;}edge[maxn];
struct Node{int x,y,z;}a[maxn];
struct node
{
int dis,pos;
bool operator < (const node &x) const
{
return x.dis<dis;
}
};
priority_queue<node> q;
bool cmp(Node x,Node y){return x.z>y.z;}
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if (ch=='-') f=-;ch=getchar();}
while(isdigit(ch)){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline void add(int from,int to,int dis)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].dis=dis;
head[from]=cnt;
}
inline void dijkstra()
{
memset(dis,0x3f,sizeof(dis));
memset(vis,,sizeof(vis));
dis[]=;q.push((node){dis[],});
while(!q.empty())
{
int now=q.top().pos;q.pop();
if (vis[now]) continue;
vis[now]=;
for (int i=head[now];i;i=edge[i].next)
{
int to=edge[i].to;
if (dis[to]>dis[now]+edge[i].dis)
{
dis[to]=dis[now]+edge[i].dis;
if (!vis[to]) q.push((node){dis[to],to});
}
}
}
}
inline int find(int x)
{
if(x==f[x]) return x;
return f[x]=find(f[x]);
}
inline void dfs(int now)
{
minn[now]=dis[now];
for (int i=head[now];i;i=edge[i].next)
{
int to=edge[i].to;
fa[to][]=now;
dfs(to);
minn[now]=min(minn[now],minn[to]);
}
}
inline void kruskal()
{
memset(head,,sizeof(head));cnt=;
sort(a+,a+m+,cmp);
for (int i=;i<=n;i++) f[i]=i;
for (int i=;i<=m;i++)
{
int xx=find(a[i].x),yy=find(a[i].y);
if (xx==yy) continue;
val[++tot]=a[i].z;
f[xx]=f[yy]=f[tot]=tot;
add(tot,xx,);add(tot,yy,);
}
dfs(tot);
}
inline void clear()
{
memset(head,,sizeof(head));cnt=;
memset(fa,,sizeof(fa));
memset(minn,0x3f,sizeof(minn));
}
signed main()
{
T=read();
while(T--)
{
clear();
n=read(),m=read();tot=n;last=;
for (int i=;i<=m;i++)
{
int u=read(),v=read(),d=read(),h=read();
add(u,v,d);add(v,u,d);
a[i].x=u,a[i].y=v,a[i].z=h;
}
dijkstra();
kruskal();
for (int j=;(<<j)<=tot;j++)
for (int i=;i<=tot;i++)
fa[i][j]=fa[fa[i][j-]][j-];
Q=read(),K=read(),S=read();
while(Q--)
{
int v=read(),p=read();
v=(v+K*last-)%n+;
p=(p+K*last)%(S+);
for (int j=;j>=;--j)
if(fa[v][j]&&val[fa[v][j]]>p) v=fa[v][j];
printf("%lld\n",last=minn[v]);
}
}
return ;
}