难点: 走过有积水的地方之后就需计算路径长了
关键算法: kruskal重构树
①原来的 kruskalkruskalkruskal 算法就是用并查集实现的，
但当我们使用 kruskal重构树的时候，
对于每次找出的不同的两个连通块的祖先，
我们都新建一个点作为两个祖先的父亲，并将当前边的边权转化为新点的点权(或指向该点的边的边权)。
②因为kruskal是贪心加边,所以对于该题来说,
如果在重构树上能从一个点抵达另一个点,那么在原图上也一定可以
③如果我们以海拔为第一关键字对边进行从大到小的排序，然后修建 kruskal重构树，
这样就弄出了一颗以海拔为关键字的小根堆。
然后对于每一棵子树，如果询问中的水位线是低于子树的根节点的，
那么此时这棵子树中的所有叶子结点都是连通的。
放到题中就是说这颗子树中任选一个点出发，
到子树中的其它点都不需要花费。(此段来自洛谷题解)
④对于每个询问,我们只需要找到该点无需花费就能走到的点(用预处理好的倍增找)中,哪个离目的地(1号点)更近,
这个预处理一下最短路就是了
上代码:
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define rg register
#define _ 200001
#define a(x) edge[x].a
#define l(x) edge[x].l
#define u(x) heap[x].u
#define it(x) heap[x].it
#define min(x,y) x<y?x:y;
using namespace std;
int n,m,record[_<<],exist[_],num_of_edges,an[_<<][],minn[_<<][],cnt,dad[_<<];
long long dis[_],New_dis[_<<];
bool used[_];
struct ppp
{
int x,y,a;
}way[_<<];
struct pp
{
int next,to,l,a;
}edge[_<<];
struct pppp
{
int u,it;
}heap[];
inline int read()
{
rg int save=,w=;rg char q=getchar();
while(q<''||q>''){if(q=='-')w=-;q=getchar();}
while(q>=''&&q<='')save=(save<<)+(save<<)+q-'',q=getchar();
return save*w;
}
inline void add(rg int from,rg int to,rg int ll,rg int aa)
{
edge[++num_of_edges]=(pp){record[from],to,ll,aa};
record[from]=num_of_edges;
}
int tail;
inline void put(rg int i,rg int ww)
{
u(++tail)=i,it(tail)=ww;
rg int d=tail;
while(d>)
{
if(it(d)<it(d>>))swap(heap[d],heap[d>>]),d>>=;
else
break;
}
}
inline void cut()
{
heap[]=heap[tail--];
it(tail+)=;
rg int d=;
while(d<tail)
{
rg int pointer=it(d<<)<it(d<<|)?(d<<):(d<<|);
if(it(d)>it(pointer))swap(heap[d],heap[pointer]),d=pointer;
else break;
}
}
int find(rg int x){if(x!=dad[x])dad[x]=find(dad[x]);return dad[x];}
inline void dijkstra()
{
for(rg int i=;i<=n;++i)used[i]=;
dis[]=;
put(,dis[]);
rg int k=;
while(tail)
{
rg pppp ss=heap[];
cut();
if(used[ss.u])continue;
used[ss.u]=;
k++;
for(rg int j=record[ss.u];j;j=edge[j].next)
{
rg int to=edge[j].to;
if(dis[to]>dis[ss.u]+edge[j].l)
{
dis[to]=dis[ss.u]+edge[j].l;
put(to,dis[to]);
}
}
if(k==n-)break;
}
}
inline bool Cwen(rg ppp x,rg ppp y){return x.a>y.a;}
int ceng;
void dfs(rg int);
inline void Kruskal()
{
rg int i,j;
for(i=;i<=(n<<);++i)dad[i]=i;
sort(way+,way+m+,Cwen);
for(i=;i<=m;++i)
{
rg int fx=find(way[i].x),fy=find(way[i].y);
if(fx!=fy)//重构树
{
add(++cnt,fx,,way[i].a);//(++cnt):新建节点
add(cnt,fy,,way[i].a);//因为之后的操作只需要从根节点遍历下来,故不建反向边
dad[fx]=dad[fy]=cnt;
if(cnt==(n<<)-)break;
}
}
ceng=log(cnt)/log();
for(i=;i<=cnt;++i)
{
if(i<=n)New_dis[i]=dis[i];
for(j=;j<=ceng;++j)
an[i][j]=,minn[i][j]=;
}
for(i=n+;i<=cnt;++i)New_dis[i]=;
//这个题目里不要找LCA,depth[]也就不需要
an[cnt][]=;//聊胜于无的一句话
dfs(cnt);//预处理点之间的最小海拔
}
void dfs(rg int i)
{
for(rg int j=;j<=ceng;++j)
{
an[i][j]=an[an[i][j-]][j-];
minn[i][j]=min(minn[i][j-],minn[an[i][j-]][j-]);
}
if(i<=n)return;//免得走到原来的图上了(在重构树里<=n的就是叶子节点,无需继续遍历)
for(rg int j=record[i];j;j=edge[j].next)
{
rg int to=edge[j].to;
if(to!=an[i][])
{
an[to][]=i;
minn[to][]=a(j);
dfs(to);
New_dis[i]=min(New_dis[i],New_dis[to]);
}
}
}
inline int jump(rg int i,rg int p)
{
for(rg int j=ceng;j>=;--j)
if(minn[i][j]>p)i=an[i][j];
return i;
}
int main()
{
rg int t=read();
while(t--)
{
n=read(),m=read();
rg int i,j;
tail=;
for(i=;i<=n;++i)dis[i]=;
for(i=;i<=(n<<);++i)it(i)=;
num_of_edges=;
for(i=;i<=(n<<);++i)record[i]=;
for(i=;i<=m;++i)
{
rg int u=read(),v=read(),l=read(),a=read();
add(u,v,l,a),add(v,u,l,a);
way[i]=(ppp){u,v,a};
}
dijkstra();
cnt=n;
Kruskal();//重构树,以海拔为关键字从大到小排序,保证可以判断一个点是否能被无耗遍历到
rg int Q=read(),K=read(),S=read();
long long lastans=;
for(i=;i<=Q;++i)
{
rg int v=read(),p=read();
v=(v+K*lastans-)%n+;
p=(p+K*lastans)%(S+);
rg int to=jump(v,p);
lastans=New_dis[to];
printf("%lld\n",lastans);
} }
return ;
}