题目大意：太长了，略
Kruskal重构树，很神奇的一个算法吧
如果两个并查集被某种条件合并，那么这个条件作为一个新的节点连接两个并查集
那么在接下来的提问中，如果某个点合法，它的所有子节点也都合法，即子节点的限制少于父节点
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <queue> 5 #define inf 0x3f3f3f3f 6 #define ll long long 7 #define il inline 8 #define N 400100 9 #define M 800100 10 using namespace std; 11 //re 12 int T,cte,ctb,n,m,tot; 13 int head[N],hbt[M],fa[M],ff[M][21],dis[N],use[N],mi[M],hei[M]; 14 struct EDGE{int to,nxt,val;}edge[M]; 15 struct Krs{int x,y,alt;}krs[N]; 16 struct BT{int to,nxt;}bt[M*2]; 17 struct node{int id,dis;}; 18 int cmpk(Krs s1,Krs s2){return s1.alt>s2.alt;} 19 il node ins(int x1,int x2){node kk;kk.id=x1,kk.dis=x2;return kk;} 20 bool operator<(const node &s1,const node &s2){return s1.dis>s2.dis;} 21 int find_fa(int x){ 22 int fx=fa[x],pre;while(fx!=fa[fx])fx=fa[fx]; 23 while(fa[x]!=fx){pre=fa[x],fa[x]=fx,x=pre;} 24 return fx; 25 } 26 int gc(){ 27 int rett=0,fh=1;char p=getchar(); 28 while(p<'0'||p>'9') {if(fh=='-')fh=-1;p=getchar();} 29 while(p>='0'&&p<='9') {rett=(rett<<3)+(rett<<1)+p-'0';p=getchar();} 30 return rett*fh; 31 } 32 void clr() 33 { 34 cte=ctb=tot=0; 35 memset(fa,0,sizeof(fa));memset(ff,0,sizeof(ff)); 36 memset(krs,0,sizeof(krs));memset(bt,0,sizeof(bt)); 37 memset(mi,0x3f,sizeof(mi));memset(edge,0,sizeof(edge)); 38 memset(head,-1,sizeof(head));memset(hbt,-1,sizeof(hbt)); 39 } 40 void abt(int u,int v){ 41 ctb++;bt[ctb].to=v; 42 bt[ctb].nxt=hbt[u],hbt[u]=ctb; 43 } 44 void ae(int u,int v,int w){ 45 cte++;edge[cte].to=v,edge[cte].val=w; 46 edge[cte].nxt=head[u],head[u]=cte; 47 } 48 void dfs_bt(int x) 49 { 50 mi[x]=dis[x]; 51 for(int j=hbt[x];j!=-1;j=bt[j].nxt){ 52 int v=bt[j].to; 53 if(v==ff[x][1]) continue; 54 ff[v][0]=v,ff[v][1]=x; 55 dfs_bt(v); 56 mi[x]=min(mi[x],min(mi[v],dis[v])); 57 } 58 } 59 void get_multip(){ 60 for(int j=2;j<=19;j++) 61 for(int i=1;i<=tot;i++) 62 ff[i][j] = ff[ ff[i][j-1] ][j-1]; 63 } 64 int multi(int x,int p){ 65 for(int j=19;j>=0;j--){ 66 if(hei[ff[x][j]]>p) x=ff[x][j]; 67 }return x; 68 } 69 void dijkstra() 70 { 71 priority_queue<node>que; 72 memset(dis,0x3f,sizeof(dis)); 73 memset(use,0,sizeof(use)); 74 dis[1]=0,que.push(ins(1,0)); 75 while(!que.empty()){ 76 node ss=que.top();que.pop(); 77 if(use[ss.id]) continue; 78 use[ss.id]=1;int x=ss.id; 79 for(int j=head[x];j!=-1;j=edge[j].nxt){ 80 int v=edge[j].to; 81 if(dis[v]>dis[x]+edge[j].val){ 82 dis[v]=dis[x]+edge[j].val; 83 if(!use[v]) que.push(ins(v,dis[v])); 84 } 85 } 86 } 87 } 88 void Kruskal() 89 { 90 int fx,fy,sum=0;tot=n; 91 for(int i=1;i<=2*n;i++) fa[i]=i; 92 sort(krs+1,krs+m+1,cmpk); 93 for(int i=1;i<=m;i++){ 94 fx=find_fa(krs[i].x),fy=find_fa(krs[i].y); 95 if(fx==fy) continue; 96 abt(++tot,fx),abt(tot,fy); 97 hei[tot]=krs[i].alt,sum++; 98 fa[fx]=tot,fa[fy]=tot; 99 if(sum==n-1) break; 100 }hei[0]=-1; 101 dfs_bt(tot); 102 get_multip(); 103 } 104 int solve(int x,int p) 105 { 106 int fx=multi(x,p); 107 return mi[fx]; 108 } 109 110 int main() 111 { 112 //freopen("data.in","r",stdin); 113 scanf("%d",&T); 114 while(T--) 115 { 116 117 n=gc(),m=gc();clr(); 118 int x,y,w,z,lst=0; 119 for(int i=1;i<=m;i++) 120 { 121 x=gc(),y=gc(),w=gc(),z=gc(); 122 ae(x,y,w),ae(y,x,w); 123 krs[i].x=x,krs[i].y=y,krs[i].alt=z; 124 } 125 dijkstra(); 126 Kruskal(); 127 int q,k,s; 128 q=gc(),k=gc(),s=gc(); 129 for(int i=1;i<=q;i++) 130 { 131 x=gc(),w=gc(); 132 x=(x+k*lst-1)%n+1; 133 w=(w+k*lst)%(s+1); 134 lst=solve(x,w); 135 printf("%d ",lst); 136 } 137 138 } 139 return 0; 140 }