1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
| const int N=4e5+10,M=4e5+10; int n,m,Q,u,v,w,l,k,s,st,lim,T; int d[N],p[N],val[N],fa[N][20],dep[N],mint[N]; struct node{ int u,v,w,l; bool operator<(const node&Q)const{ return l>Q.l; } }ed[M]; vector<pi> as[N]; vector<int> tr[N];
void kru() { memset(val,0,sizeof val); for(int i=1;i<=2*n-1;i++) tr[i].clear(); for(int i=1;i<=2*n-1;i++) p[i]=i; sort(ed+1,ed+1+m); T=n; for(int i=1;i<=m;i++) { int a=ed[i].u,b=ed[i].v,c=ed[i].l; int x=find(a),y=find(b); if(x!=y) { p[x]=p[y]=++T; tr[T].pb(x),tr[T].pb(y); val[T]=c; } if(T==2*n-1) break; } }
int dfs(int x,int rt) { dep[x]=dep[rt]+1; fa[x][0]=rt,mint[x]=d[x]; for(int k=1;(1<<k)<=dep[x];k++) fa[x][k]=fa[fa[x][k-1]][k-1]; for(auto &v:tr[x]) mint[x]=min(mint[x],dfs(v,x)); return mint[x]; }
void prework() { priority_queue<pi,vector<pi>,greater<pi>> q; memset(d,0x3f,sizeof d); memset(p,0,sizeof p); d[1]=0; q.push({0,1}); while(q.size()) { auto t=q.top(); q.pop(); int x=t.se; if(p[x]) continue; p[x]=1; go(it) { int v=it.fi,w=it.se; if(d[v]>d[x]+w) { d[v]=d[x]+w; q.push({d[v],v}); } } } kru(); memset(mint,0x3f,sizeof mint); memset(fa,0,sizeof fa); memset(dep,0,sizeof dep); dfs(T,0); }
int query(int x) { int ans=mint[st]; int li=log2(dep[x]); for(int k=li;k>=0;k--) if(val[fa[x][k]]>lim) { ans=min(ans,mint[fa[x][k]]); x=fa[x][k]; } return ans; }
void solve() { n=fr(),m=fr(); for(int i=1;i<=n;i++) as[i].clear(); for(int i=1;i<=m;i++) { u=fr(),v=fr(),w=fr(),l=fr(); as[u].pb({v,w}),as[v].pb({u,w}); ed[i]={u,v,w,l}; } prework(); int lt=0; Q=fr(),k=fr(),s=fr(); while(Q--) { int v0=fr(),p0=fr(); st=(v0+k*lt-1)%n+1; lim=(p0+k*lt)%(s+1); fw(lt=query(st)),nl; } }
signed main() { int _T=fr(); while(_T--) solve();
return 0; }
|