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 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139
| #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std;
const int N=2e5,M=4e5; typedef long long ll; const ll INF=(1ll<<60);
int cas; int n,m,fn,q,tmp; int ch[N*2+3][2],val[N*2+3],pre[N*2+3][20]; ll dis[N+3],mn[N*2+3]; bool fix[N+3];
struct DSU{ int fa[N+3],head[N+3]; void Init(){ for(int i=1;i<=n;i++){ fa[i]=head[i]=i; mn[i]=INF; } } int FindFa(int u){ if(u==fa[u]) return u; return fa[u]=FindFa(fa[u]); } bool Merge(int u,int v,int wgt){ int fu=FindFa(u),fv=FindFa(v); if(fu==fv) return false; fn++; ch[fn][0]=head[fu]; ch[fn][1]=head[fv]; val[fn]=wgt; head[fv]=fn; fa[fu]=fv; return true; } }D_; struct GNODE{ int to,len;GNODE *nxt; GNODE(){} GNODE(int _t,int _l,GNODE *_n):to(_t),len(_l),nxt(_n){} }; struct GRAPH{ GNODE pol[M*2+3],*ncnt,*head[N+3]; void Init(){ for(int i=1;i<=n;i++) head[i]=NULL; ncnt=pol; } void AddEdge(int u,int v,int len){ GNODE *p=++ncnt,*q=++ncnt; *p=GNODE(v,len,head[u]);head[u]=p; *q=GNODE(u,len,head[v]);head[v]=q; } GNODE* operator [](int id){return head[id];} }G_; struct EDGE{ int u,v,wgt; EDGE(){} EDGE(int _u,int _v,int _w):u(_u),v(_v),wgt(_w){} }E_[M+3];
bool cmpEDGE(const EDGE &A,const EDGE &B){return A.wgt>B.wgt;} void Kruskal(){ sort(E_+1,E_+1+m,cmpEDGE); for(int i=1;i<=m;i++) D_.Merge(E_[i].u,E_[i].v,E_[i].wgt); } void Dijkstra(){ priority_queue< pair<ll,int> > que; que.push(make_pair(dis[1]=0,1)); while(!que.empty()){ int u=que.top().second;que.pop(); if(fix[u]) continue; fix[u]=true; for(GNODE *it=G_[u];it;it=it->nxt){ int v=it->to; if(!fix[v] && dis[v]>dis[u]+it->len) que.push(make_pair(-(dis[v]=dis[u]+it->len),v)); } } } ll DFS(int u,int fa){ pre[u][0]=fa; for(int i=1;i<=19;i++) pre[u][i]=pre[pre[u][i-1]][i-1]; if(u<=n) return mn[u]=dis[u]; return mn[u]=min(DFS(ch[u][0],u),DFS(ch[u][1],u)); } void Init(){ memset(pre,0,sizeof pre); memset(mn,0x3f,sizeof mn); memset(fix,false,sizeof fix); memset(dis,0x3f,sizeof dis); memset(ch,0,sizeof ch); G_.Init(); D_.Init(); fn=n; } int Fetch(int u,int lim){ for(int i=19;i>=0;i--) if(pre[u][i] && val[pre[u][i]]>lim) u=pre[u][i]; return u; } int main(){ scanf("%d",&cas); while(cas--){ scanf("%d%d",&n,&m); Init(); for(int i=1;i<=m;i++){ int len; scanf("%d%d%d%d",&E_[i].u,&E_[i].v,&len,&E_[i].wgt); G_.AddEdge(E_[i].u,E_[i].v,len); } Dijkstra(); Kruskal(); for(int i=fn;i;i--) if(!pre[i][0]) DFS(i,0); int vS; scanf("%d%d%d",&q,&tmp,&vS); long long las=-1; while(q--){ int frm,hgt; scanf("%d%d",&frm,&hgt); if(las!=-1){ frm=(frm+tmp*las-1)%n+1; hgt=(hgt+tmp*las)%(vS+1); } printf("%lld\n",las=mn[Fetch(frm,hgt)]); } } return 0; }
|