题目 N<=2e5 M<=4e5 Q<=4e5；
思路：从点v出发走海拔超过p的边。就是kruskal重构树了。先dijksta处理每个节点到出发点1的最短路d[]. 然后dfs建立fa[][]数组时顺便求出每个节点所掌管的子节点以及他自己 离出发点1最近的节点。这里有些要注意。 if(d[son[y]]<d[son[x]]) son[x]=son[y]…记住这个把。。。
//P4768归程(kruskal重构树倍增+dijkstra预处理+dfs时预处理哪个子节点最近) //q次询问: 给点u,p u只能跑跑边长>p的边 只能走路 问回到1点最少走多少? N<=2e5 M<=4e5 Q<=4e5; #include<bits/stdc++.h> #define m(a,b) memset(a,b,sizeof a) using namespace std; typedef long long ll; const int N=2e5+5,M=4e5+5,K=20; const ll INF=(ll)(1)<<(ll)(61); struct _Edge{int u,v,l,w;}e[M]; inline int cmp(_Edge x,_Edge y){return x.w>y.w;} struct Edge{int to,nex;}edge[N<<1];int head[N<<1],tot; inline void add(int from,int to){ edge[++tot]=(Edge){to,head[from]};head[from]=tot; } struct Edg{int to,len,nex;}edg[M<<1];int hed[N],ttt; inline void ad(int from,int to,int len){ edg[++ttt]=(Edg){to,len,hed[from]};hed[from]=ttt; edg[++ttt]=(Edg){from,len,hed[to]};hed[to]=ttt; } int f[N<<1],val[N],node; inline int seek(int x){return (x==f[x])?x:(f[x]=seek(f[x]));} int n,m; void ex_kruskal(){ for(int i=1;i<=n;++i) f[i]=i; sort(e+1,e+m+1,cmp); int cnt=0;node=n; for(int i=1;i<=m;++i){ int u=e[i].u,v=e[i].v,fu,fv; fu=seek(u),fv=seek(v); if(fu==fv) continue; val[(++node)-n]=e[i].w,++cnt; f[node]=node,f[fu]=node,f[fv]=node; add(node,fu),add(node,fv); if(cnt==(n-1)) break; } } priority_queue<pair<int,int> >q;ll d[N<<1]; void dijkstra(int s){ for(int i=1;i<=2*n;++i) d[i]=INF;//也要初始化[n+1,2*n]. d[s]=0,q.push(make_pair(0,s)); while(!q.empty()){ int x=q.top().second;q.pop(); for(int i=hed[x];i;i=edg[i].nex){ int y=edg[i].to,l=edg[i].len; if(d[y]>d[x]+l){d[y]=d[x]+l,q.push(make_pair(-d[y],y));} } } } int dep[N<<1],fa[N<<1][K+5],son[N<<1]; void dfs(int x){ for(int j=1;(1<<j)<=dep[x];j++) fa[x][j]=fa[fa[x][j-1]][j-1]; son[x]=x; for(int i=head[x];i;i=edge[i].nex){ int y=edge[i].to; dep[y]=dep[x]+1,fa[y][0]=x; dfs(y); if(d[son[y]]<d[son[x]]) son[x]=son[y]; } } inline int BZ(int x,ll w){ for(int j=K;j>=0;j--) if(fa[x][j]!=-1&&val[fa[x][j]-n]>w) x=fa[x][j]; return x; } void init(){ m(head,0),tot=0,m(hed,0),ttt=0; m(fa,-1); for(int i=1;i<=2*n;++i) son[i]=i; } int main(){ int T;scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m);init(); for(int i=1;i<=m;++i) scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].l,&e[i].w),ad(e[i].u,e[i].v,e[i].l); ex_kruskal(); dijkstra(1);fa[node][0]=node,dep[node]=0,dfs(node); int q,k,s;scanf("%d%d%d",&q,&k,&s);ll las=0; while(q--){ int v;ll p;scanf("%d%lld",&v,&p); v=(v+k*las-1)%n+1,p=(p+k*las)%(s+1); v=BZ(v,p);printf("%lld\n",las=d[son[v]]); } } }