首先肯定要预处理出每一个点到1的最短路（别写spfa）
然后以海拔为边权，建一棵kruskal重构树
用倍增找到vi最后一个小于pi的祖先，然后在子树中取min（预处理）
View Code
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 400005 4 struct ji1{ 5 int x,y,z; 6 bool operator < (const ji1 &k)const{ 7 return z>k.z; 8 } 9 }e[N]; 10 struct ji2{ 11 int nex,to,len; 12 }edge[N<<1]; 13 struct ji3{ 14 int k,d; 15 bool operator < (const ji3 &x)const{ 16 return d>x.d; 17 } 18 }; 19 priority_queue<ji3>q; 20 int T,E,n,m,x,y,z,w,ans,head[N],d[N],vis[N],v[N],ls[N],rs[N],f[N][21]; 21 int find(int k){ 22 if (k==f[k][0])return k; 23 return f[k][0]=find(f[k][0]); 24 } 25 void add(int x,int y,int z){ 26 edge[E].nex=head[x]; 27 edge[E].to=y; 28 edge[E].len=z; 29 head[x]=E++; 30 } 31 void dij(){ 32 for(int i=2;i<=n;i++)d[i]=2e9; 33 memset(vis,0,sizeof(vis)); 34 q.push(ji3{1,0}); 35 while (!q.empty()){ 36 int k=q.top().k; 37 q.pop(); 38 if (vis[k])continue; 39 vis[k]=1; 40 for(int i=head[k];i!=-1;i=edge[i].nex){ 41 int v=edge[i].to; 42 if (d[v]>d[k]+edge[i].len)q.push(ji3{v,d[v]=d[k]+edge[i].len}); 43 } 44 } 45 } 46 void dfs(int k){ 47 for(int i=1;i<=20;i++)f[k][i]=f[f[k][i-1]][i-1]; 48 if (k<=n)return; 49 f[ls[k]][0]=f[rs[k]][0]=k; 50 dfs(ls[k]); 51 dfs(rs[k]); 52 } 53 int query(int k,int w){ 54 for(int i=20;i>=0;i--) 55 if (w<v[f[k][i]])k=f[k][i]; 56 return d[k]; 57 } 58 int main(){ 59 scanf("%d",&T); 60 while (T--){ 61 scanf("%d%d",&n,&m); 62 memset(head,-1,sizeof(head)); 63 E=ans=0; 64 for(int i=1;i<=m;i++){ 65 scanf("%d%d%d%d",&x,&y,&z,&w); 66 add(x,y,z); 67 add(y,x,z); 68 e[i]=ji1{x,y,w}; 69 } 70 dij(); 71 for(int i=1;i<2*n;i++)f[i][0]=i; 72 sort(e+1,e+m+1); 73 for(int i=1;i<=m;i++){ 74 x=find(e[i].x); 75 y=find(e[i].y); 76 if (x==y)continue; 77 v[++n]=e[i].z; 78 d[n]=min(d[x],d[y]); 79 ls[n]=x; 80 rs[n]=y; 81 f[x][0]=f[y][0]=n; 82 } 83 n=n/2+1; 84 dfs(2*n-1); 85 scanf("%d%d%d",&m,&z,&w); 86 for(int i=1;i<=m;i++){ 87 scanf("%d%d",&x,&y); 88 printf("%d\n",ans=query((x+z*ans-1)%n+1,(y+z*ans)%(w+1))); 89 } 90 } 91 }