归程
Luogu
LOJ
UOJ
BZOJ
不难发现一定是先开车走一段路直到下条边海拔不超过水位，然后下车沿最短路走到\(1\)号点。
按海拔降序建出Kruskal重构树，对于一次询问，找到\(v\)的祖先中深度最低的海拔高于水位低的点\(u\)，那么\(u\)的子树中的叶子节点就是\(v\)可以开车到的点。
预处理每个点到\(1\)号点的最短路\(dis\)，然后维护每个节点子树中的叶子节点最小\(dis\)即可。
#include<bits/stdc++.h>
#define M 400007
#define N 200007
using namespace std;
namespace IO
{
char ibuf[(1<<21)+1],obuf[(1<<21)+1],st[15],*iS,*iT,*oS=obuf,*oT=obuf+(1<<21);
char Get() { return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++); }
void Flush() { fwrite(obuf,1,oS-obuf,stdout),oS=obuf; }
void Put(char x) { *oS++=x; if(oS==oT) Flush(); }
int read(){int x=0;char ch=Get();while(ch>57||ch<48)ch=Get();while(ch>=48&&ch<=57)x=x*10+(ch^48),ch=Get();return x;}
void write(int x) {int top=0; if(!x) Put('0'); while(x) st[++top]=(x%10)+48,x/=10; while(top) Put(st[top--]); Put('\n'); }
}
using namespace IO;
struct EDGE{int u,v,w;}Edge[M];
int operator<(EDGE a,EDGE b){return a.w>b.w;}
struct dot{int u,d;};
int operator<(dot a,dot b){return a.d>b.d;}
priority_queue<dot>q;
int tot,head[N<<1],ver[M<<1],Next[M<<1],edge[M<<1],dis[N<<1],vis[N],dep[N<<1],val[N<<1],fa[N<<1],f[N<<1][20];
void add(int u,int v,int w=0){ver[++tot]=v,Next[tot]=head[u],edge[tot]=w,head[u]=tot;}
int Find(int x){return x==fa[x]? x:fa[x]=Find(fa[x]);}
void dfs(int u,int Fa)
{
dep[u]=dep[Fa]+1,f[u][0]=Fa;
for(int i=1;i<=19;++i) f[u][i]=f[f[u][i-1]][i-1];
for(int i=head[u],v;i;i=Next[i]) dfs(v=ver[i],u),dis[u]=min(dis[u],dis[v]);
}
int query(int u,int p)
{
for(int i=19;~i;--i) if((dep[u]>1<<i)&&val[f[u][i]]>p) u=f[u][i];
return dis[u];
}
int main()
{
int T,i,n,m,u,v,w,l,lastans,cnt,Q,K,S,num;
for(T=read();T;--T)
{
num=lastans=tot=0,n=read(),m=read(),memset(head,0,sizeof head),memset(f,0,sizeof f);
for(i=1;i<=m;++i) u=read(),v=read(),l=read(),w=read(),add(u,v,l),add(v,u,l),Edge[i]=EDGE{u,v,w};
memset(vis,0,sizeof vis),memset(dis,0x3f,sizeof dis),dis[1]=0,q.push(dot{1,0});
while(!q.empty())
{
u=q.top().u,q.pop();
if(vis[u]) continue;
for(vis[u]=1,i=head[u];i;i=Next[i]) if(!vis[v=ver[i]]&&dis[v]>dis[u]+edge[i]) dis[v]=dis[u]+edge[i],q.push(dot{v,dis[v]});
}
memset(head,0,sizeof head),tot=0,cnt=n,sort(Edge+1,Edge+m+1);
for(i=1;i<=n<<1;++i) fa[i]=i;
for(i=1;i<=m;++i) if((u=Find(Edge[i].u))^(v=Find(Edge[i].v))){val[++cnt]=Edge[i].w,fa[u]=fa[v]=cnt,add(cnt,u),add(cnt,v),++num;if(num==n-1)break;};
dfs(cnt,0);
Q=read(),K=read(),S=read();
while(Q--) u=(K*lastans+read()-1)%n+1,v=(K*lastans+read())%(S+1),write(lastans=query(u,v));
}
return Flush(),0;
}