题目大意：给定一张$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(qlog n+n))$
代码：
#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=2000005; int n,m,Q,T,K,S,val[maxn],tot,minn[maxn],f[maxn],fa[maxn][23],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=0,f=1;char ch=getchar(); while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';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,0,sizeof(vis)); dis[1]=0;q.push((node){dis[1],1}); while(!q.empty()) { int now=q.top().pos;q.pop(); if (vis[now]) continue; vis[now]=1; 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][0]=now; dfs(to); minn[now]=min(minn[now],minn[to]); } } inline void kruskal() { memset(head,0,sizeof(head));cnt=1; sort(a+1,a+m+1,cmp); for (int i=1;i<=n;i++) f[i]=i; for (int i=1;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,0);add(tot,yy,0); } dfs(tot); } inline void clear() { memset(head,0,sizeof(head));cnt=1; memset(fa,0,sizeof(fa)); memset(minn,0x3f,sizeof(minn)); } signed main() { T=read(); while(T--) { clear(); n=read(),m=read();tot=n;last=0; for (int i=1;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=1;(1<<j)<=tot;j++) for (int i=1;i<=tot;i++) fa[i][j]=fa[fa[i][j-1]][j-1]; Q=read(),K=read(),S=read(); while(Q--) { int v=read(),p=read(); v=(v+K*last-1)%n+1; p=(p+K*last)%(S+1); for (int j=22;j>=0;--j) if(fa[v][j]&&val[fa[v][j]]>p) v=fa[v][j]; printf("%lld ",last=minn[v]); } } return 0; }