题面
https://www.luogu.org/problem/P4768
题解
#include<cstdio> #include<iostream> #include<vector> #include<queue> #include<cstring> #include<algorithm> using namespace std; int dis[205000]; bool vis[205000]; inline int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } struct node { int lb,rb,lson,rson,fa,mindis,dep; } tree[20000500]; struct edge { int u,v,l,h; bool operator < (const edge rhs) const { return h<rhs.h; } } a[405000]; struct node2 { int u,d; bool operator < (const node2 rhs) const { return d>rhs.d; } }; vector<int> to[205000],len[205000]; int n,m,cnt,root[405000]; void dij() { register int i; priority_queue<node2> pq; while (!pq.empty()) pq.pop(); dis[1]=0; for (i=2;i<=n;i++) dis[i]=2e9+5; memset(vis,0,sizeof(vis)); pq.push((node2){1,0}); while (!pq.empty()) { node2 x=pq.top(); pq.pop(); if (vis[x.u]) continue; dis[x.u]=x.d; vis[x.u]=true; for (i=to[x.u].size()-1;i>=0;i--) if (x.d+len[x.u][i]<dis[to[x.u][i]]) { dis[to[x.u][i]]=x.d+len[x.u][i]; pq.push((node2){to[x.u][i],dis[to[x.u][i]]}); } } } void maketree(register int now,register int l,register int r){ tree[now].lb=l; tree[now].rb=r; if (l==r) { tree[now].fa=l; tree[now].mindis=dis[l]; tree[now].dep=1; return; } // fa to a loc register int mid=(l+r)/2; tree[now].lson=cnt+1; maketree(++cnt,l,mid); tree[now].rson=cnt+1; maketree(++cnt,mid+1,r); } void build(register int now,register int old,register int uu,register int vv) { tree[now]=tree[old]; register int l=tree[now].lb,r=tree[now].rb,mid=(l+r)/2; if (l==r) return; if ((l<=uu&&uu<=mid)||(l<=vv&&vv<=mid)) tree[now].lson=cnt+1,build(++cnt,tree[old].lson,uu,vv); if ((mid+1<=uu&&uu<=r)||(mid+1<=vv&&vv<=r)) tree[now].rson=cnt+1,build(++cnt,tree[old].rson,uu,vv); } int find(register int now,register int loc) { //return a poregister int if (tree[now].lb==tree[now].rb) return now; if (loc<=(tree[now].lb+tree[now].rb)/2) return find(tree[now].lson,loc); else return find(tree[now].rson,loc); } int findroot(register int now,register int cur) { //return a loc if (tree[now].fa==tree[now].lb) return tree[now].lb; else return findroot(find(root[cur],tree[now].fa),cur); } void kru(){ register int i,j,uu,vv; sort(a+1,a+m+1); cnt=0; root[m+1]=1; maketree(++cnt,1,n); for (i=m;i>=1;i--) { uu=findroot(find(root[i+1],a[i].u),i+1); vv=findroot(find(root[i+1],a[i].v),i+1); if (uu==vv) { root[i]=root[i+1]; continue; } root[i]=cnt+1; build(++cnt,root[i+1],uu,vv); uu=find(root[i],uu); vv=find(root[i],vv); if (tree[uu].dep<tree[vv].dep) { tree[vv].dep=max(tree[vv].dep,tree[uu].dep+1); tree[vv].mindis=min(tree[vv].mindis,tree[uu].mindis); tree[uu].fa=tree[vv].lb; } else { tree[uu].dep=max(tree[uu].dep,tree[vv].dep+1); tree[uu].mindis=min(tree[uu].mindis,tree[vv].mindis); tree[vv].fa=tree[uu].lb; } } } int main(){ register int T,i,j,v,q,k,s,p,lastans; T=read(); while (T--) { n=read(); m=read(); for (i=1;i<=n;i++) to[i].clear(),len[i].clear(); for (i=1;i<=m;i++) { a[i].u=read(); a[i].v=read(); a[i].l=read(); a[i].h=read(); to[a[i].u].push_back(a[i].v); len[a[i].u].push_back(a[i].l); to[a[i].v].push_back(a[i].u); len[a[i].v].push_back(a[i].l); } dij(); kru(); q=read(); k=read(); s=read(); lastans=0; a[m+1].h=2e9+5; for (i=1;i<=q;i++) { v=read(); p=read(); v=(v+k*lastans-1)%n+1; p=(p+k*lastans)%(s+1); register int cur=upper_bound(a+1,a+m+2,(edge){0,0,0,p})-a; register int ans=find(root[cur],findroot(find(root[cur],v),cur)); printf("%d ",tree[ans].mindis); lastans=tree[ans].mindis; } } }