题意：给一张无向联通图，每条边有长度和高度，每次询问在高度大于p的边，从v点能到达的所有点到1号点的最短距离（强制在线）
首先dijkstra求出每个点到1号点的距离
易知：如果我按高度从高到低给边排序然后用kruskal的方法做出一棵生成树，那么在高度大于p的条件下，在原图中联通的两点在生成树中依旧联通
于是就可以在做kruskal的时候建一个叫做重构树的东西，在用并查集维护联通块的同时维护一个树结构：
对于每条边，若原本两端点u,v不连通，则新建一个节点t，设a,b为u,v在并查集中的祖先，令并查集和树结构中fa[a]=fa[b]=t，同时记下树中t的两个孩子为a,b，以及t的高度与边的高度相同
这样，树中的每棵子树的叶节点都是连通的，并且树中深度越深，节点对应边的高度就越大
dfs一下就可以处理出每个子树对应联通块的距1号点的最近距离。
然后对于点v，就可以倍增找出高度恰大于p的那个节点，就是最后结果
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 #include<vector> 6 #define LL long long int 7 #define pa pair<int,int> 8 using namespace std; 9 const int maxn=2e5+10,logn=18,maxm=4e5+10,inf=0x3f3f3f3f; 10 11 int rd(){ 12 int x=0;char c=getchar(); 13 while(c<'0'||c>'9') c=getchar(); 14 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 15 return x; 16 } 17 18 struct Edge{ 19 int a,b,l,h,ne; 20 }eg[maxm*2]; 21 struct Node{ 22 int fa[logn],v,h,ch[2]; 23 }tr[maxn*2]; 24 int bcj[maxn*2],tct; 25 int N,M,Q,K,S; 26 int egh[maxn],ect; 27 int dis[maxn]; 28 priority_queue<pa,vector<pa>,greater<pa> > q; 29 30 inline void adeg(int a,int b,int l,int h){ 31 eg[ect].a=a;eg[ect].b=b;eg[ect].l=l;eg[ect].h=h;eg[ect].ne=egh[a];egh[a]=ect++; 32 } 33 34 void dijkstra(){ 35 memset(dis,127,sizeof(dis));dis[1]=0; 36 q.push(make_pair(0,1)); 37 while(!q.empty()){ 38 int p=q.top().second;q.pop(); 39 for(int i=egh[p];i!=-1;i=eg[i].ne){ 40 int b=eg[i].b; 41 if(dis[b]>dis[p]+eg[i].l){ 42 dis[b]=dis[p]+eg[i].l; 43 q.push(make_pair(dis[b],b)); 44 } 45 } 46 } 47 } 48 49 int getf(int x){return x==bcj[x]?x:bcj[x]=getf(bcj[x]);} 50 51 void kruskal(){ 52 memset(tr,0,sizeof(tr)); 53 for(int i=1;i<=N*2;i++) bcj[i]=i,tr[i].v=inf;tct=N; 54 for(int i=1,n=1;i<ect&&n<N;i++){ 55 int a=getf(eg[i].a),b=getf(eg[i].b); 56 if(a==b) continue; 57 bcj[a]=bcj[b]=++tct; 58 tr[a].fa[0]=tr[b].fa[0]=tct; 59 tr[tct].ch[0]=a;tr[tct].ch[1]=b; 60 tr[tct].h=eg[i].h;n++; 61 } 62 } 63 64 void dfs(int x){ 65 for(int i=0;i<logn-1;i++){ 66 if(!tr[tr[x].fa[i]].fa[i]) break; 67 tr[x].fa[i+1]=tr[tr[x].fa[i]].fa[i]; 68 } 69 if(tr[x].ch[0]){ 70 dfs(tr[x].ch[0]);dfs(tr[x].ch[1]); 71 tr[x].v=min(tr[tr[x].ch[0]].v,tr[tr[x].ch[1]].v); 72 }else tr[x].v=dis[x]; 73 } 74 75 inline bool cmp(Edge a,Edge b){ 76 return a.h>b.h; 77 } 78 79 int query(int v,int p){ 80 for(int i=logn-1;i>=0;i--){ 81 if(tr[v].fa[i]&&tr[tr[v].fa[i]].h>p) v=tr[v].fa[i]; 82 }return tr[v].v; 83 } 84 85 int main(){ 86 int i,j,k; 87 //freopen("return.in","r",stdin); 88 for(int T=rd();T;T--){ 89 N=rd(),M=rd();memset(egh,-1,sizeof(egh));ect=0; 90 for(i=1;i<=M;i++){ 91 int a=rd(),b=rd(),c=rd(),d=rd(); 92 adeg(a,b,c,d);adeg(b,a,c,d); 93 }dijkstra(); 94 sort(eg,eg+ect,cmp);kruskal();dfs(tct); 95 Q=rd(),K=rd(),S=rd(); 96 int lastans=0; 97 for(i=1;i<=Q;i++){ 98 int v=(rd()+K*lastans-1)%N+1; 99 int p=(rd()+K*lastans)%(S+1); 100 printf("%d ",lastans=query(v,p)); 101 } 102 } 103 }