题面传送门 一不小心抢了最优解。 首先跑出 1 1 1到所有点的最短路，因为那个梗在先，所以用堆优化dj 然后这道题显然要让我们求最小瓶颈路之类的东西。 所以就可以建出克鲁斯卡尔重构树。在树上倍增。 同时处理子树内距离最小值。倍增到的那个点的值就是答案了。 代码实现:
#include<cstdio> #include<queue> #include<algorithm> #include<cstring> #define min(a,b) ((a)<(b)?(a):(b)) using namespace std; int n,m,k,x,y,z,zs,gf[800039],t,g[800039],fa[800039][20],lg[800039],dis[800039],head,cur,un,wn,tot,qs,mod; unsigned int d[800039],lastans; struct ques{ int to;unsigned int w; bool operator <(const ques &x) const{return w>x.w;} }now; priority_queue<ques> q; struct yyy{int to,w,z;}tmp; struct ljb{ int head,h[800039]; yyy f[1600039]; inline void add(int x,int y,int z){ f[++head]=(yyy){y,z,h[x]}; h[x]=head; } }s; struct tree{int x,y,z;}f[400039]; inline bool cmp(tree x,tree y){return x.z>y.z;} inline void read(int &x){ char s=getchar();x=0; while(s<'0'||s>'9') s=getchar(); while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+(s^48),s=getchar(); } inline void dj(){ q.push((ques){1,0});d[1]=0; while(!q.empty()){ now=q.top();q.pop(); for(cur=s.h[now.to];cur;cur=tmp.z){ tmp=s.f[cur]; if(d[tmp.to]>d[now.to]+tmp.w) d[tmp.to]=d[now.to]+tmp.w,q.push((ques){tmp.to,d[tmp.to]}); } } } inline void dfs(int x,int last){ int i,cur;yyy tmp;fa[x][0]=last;dis[x]=dis[last]+1; for(i=1;i<=lg[dis[x]];i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for(cur=s.h[x];cur;cur=tmp.z){ tmp=s.f[cur]; if(tmp.to!=last)dfs(tmp.to,x),d[x]=min(d[x],d[tmp.to]); } } inline unsigned int lca(int x,int y){ int i; for(i=lg[dis[x]];i>=0;i--) if(g[fa[x][i]]>y) x=fa[x][i]; return d[x]; } inline int find(int x){return gf[x]==x?x:gf[x]=find(gf[x]);} int main(){ // freopen("1.in","r",stdin); // freopen("1.out","w",stdout); register int i; scanf("%d",&t); for(i=1;i<=4e5;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i); while(t--){ scanf("%d%d",&n,&m);memset(s.h,0,sizeof(s.h));s.head=0; for(i=1;i<=2*n;i++) d[i]=1e10;head=n; for(i=1;i<=2*n;i++) gf[i]=i; for(i=1;i<=m;i++) read(x),read(y),read(z),read(zs),s.add(x,y,z),s.add(y,x,z),f[i]=(tree){x,y,zs}; dj();memset(s.h,0,sizeof(s.h));s.head=0; sort(f+1,f+m+1,cmp);tot=0; for(i=1;i<=m;i++){ un=find(f[i].x);wn=find(f[i].y); if(un!=wn){ gf[un]=gf[wn]=++head; s.add(un,head,0);s.add(head,un,0);s.add(wn,head,0);s.add(head,wn,0); g[head]=f[i].z; tot++; if(tot==n-1) break; } } dfs(head,0);lastans=0; scanf("%d%d%d",&qs,&k,&mod); while(qs--){ read(x);read(y); x=(x+k*lastans-1)%n+1;y=(y+k*lastans)%(mod+1); lastans=lca(x,y); printf("%u\n",lastans); } } }