这是一个悲伤的题目，自这道题后，\(\text{Noi}\) 再无 \(\text{SPFA}\)。
首先讲一下重构树是啥。
重构树是基于 \(\text{kurskal 生成树}\) 算法的一棵树，对于每一次合并一条边，用一个新的节点，连接边的两个端点连起来，用新的点替换这两个点进行下次合并即可，新的点点权为合并的边权。（画个图即可）
重构树有一个特点，即是原图中两个点间的所有路径中每个路径的边权最小的最大（最大的最小）即是两个点在重构树的 \(\text{LCA}\)。（画图解决）
所以本题怎么去使用重构树呢。
首先对于海拔，我们先建一棵最大生成树，并建重构树，可以证明，重构树中深度越小，海拔越小。
那么对于一个询问的点 \(v\) 的祖先 \(t\)，如果 \(t\) 的海拔大于水位线，且 \(t\) 的父亲海拔小于等于水位线，那么在 \(t\) 以下的所有点都是可以开车达到的。
所以我们先从 \(1\) 节点开始跑一次最短路，对于每一次询问，找到重构树中规定的父亲，这个步骤可以提前用倍增优化，最后找到这个节点内所有子节点中与 \(1\) 距离最短的节点，选择从这个节点开始步行，最短的节点可以搜索一遍重构树进行处理。
然后如果没怎么弄懂可以看看代码。
时间复杂度：\(O((m+q)\times\log(n))\)。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
const int N=8e5+5;
int n,m,qs,cnt,t[N],dis[N],p[N][25],g[N][25],f[N];
struct node3
{
int name,data;
};
priority_queue<node3>q;
bool operator <(node3 fi,node3 se)
{
return fi.data>se.data;
}
struct node
{
int from,to,data1,data2;
}b[N];
int cmp(node fi,node se)
{
return fi.data2>se.data2;
}
struct node2
{
int to,data1,data2;
};
vector<node2>a[N];
vector<int>c[N];
int afind(int x)
{
if(x==f[x])return x;
return f[x]=afind(f[x]);
}
void krus()
{
cnt=n;
for(int i=1;i<=2*n;i++)f[i]=i;
sort(b+1,b+1+m,cmp);
for(int i=1;i<=m;i++)
{
int u=b[i].from,v=b[i].to,w2=b[i].data2;
if(afind(u)==afind(v))continue;
cnt++;
dis[cnt]=min(dis[afind(u)],dis[afind(v)]);
c[cnt].push_back(afind(u));
c[cnt].push_back(afind(v));
f[afind(u)]=f[afind(v)]=cnt;
t[cnt]=w2;
}
}
void dijstra()
{
for(int i=2;i<=n;i++)dis[i]=1e18;
q.push({1,0});
while(!q.empty())
{
int x=q.top().name;
q.pop();
int len=a[x].size();
for(int i=0;i<len;i++)
{
if(a[x][i].data1+dis[x]<dis[a[x][i].to])
{
dis[a[x][i].to]=dis[x]+a[x][i].data1;
q.push({a[x][i].to,dis[a[x][i].to]});
}
}
}
}
void dfs(int x,int fa)
{
int len=c[x].size();
p[x][0]=fa;
g[x][0]=t[fa];
for(int i=1;i<=20;i++)p[x][i]=p[p[x][i-1]][i-1],g[x][i]=t[p[x][i]];
for(int i=0;i<len;i++)dfs(c[x][i],x);
}
int findans(int x,int y)
{
for(int i=20;i>=0;i--)if(g[x][i]>y)x=p[x][i];
return x;
}
signed main()
{
int T;
scanf("%lld",&T);
while(T--)
{
for(int i=1;i<=2*n;i++)a[i].clear(),c[i].clear();
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v,dat1,dat2;
scanf("%lld%lld%lld%lld",&u,&v,&dat1,&dat2);
a[u].push_back({v,dat1,dat2});
a[v].push_back({u,dat1,dat2});
b[i]={u,v,dat1,dat2};
}
dijstra();
krus();
dfs(cnt,0);
int k,s;
scanf("%lld%lld%lld",&qs,&k,&s);
int lastans=0;
for(int i=1;i<=qs;i++)
{
int x,y;
scanf("%lld%lld",&x,&y);
x=(x+k*lastans-1)%n+1;
y=(y+k*lastans)%(s+1);
int ans=dis[findans(x,y)];
printf("%lld\n",ans);
lastans=ans;
}
}
return 0;
}
/*
1
4 3
1 2 50 1
2 3 100 2
3 4 50 1
5 0 2
3 0
2 1
4 1
3 1
3 2
*/