今天也要踏上归程了呢~（题外话
kruskal重构树！当时就听学长们说过是重构树辣所以做起来也很快233
就是我们按照a建最大生成树 这样话呢我们就可以通过生成树走到尽量多的点啦
然后呢就是从这个子树内走到1的最短路 提前处理出来然后就是子树最小值啦w
附代码。（些许丑陋（
//Love and Freedom. #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #include<queue> #define ll long long #define inf 20021225 #define N 400010 #define M 800010 using namespace std; struct edge{int x,y,v;}g[M]; struct edg{int to,lt,v;}e[M],t[N]; struct node { int id,v; node(){} node(int _id,int _v){id=_id,v=_v;} }; bool operator <(node a,node b){return a.v>b.v;} priority_queue<node> q; int cnt,in[N]; void add(int x,int y,int l,int a) { e[++cnt].to=y; e[cnt].lt=in[x]; e[cnt].v=l; in[x]=cnt; e[++cnt].to=x; e[cnt].lt=in[y]; e[cnt].v=l; in[y]=cnt; g[cnt>>1].x=x; g[cnt>>1].y=y; g[cnt>>1].v=a; } void tree(int x,int y) { t[++cnt].to=y; t[cnt].lt=in[x]; in[x]=cnt; } int bel[N],n,val[N],m; bool vis[N]; int find(int x) { //printf("%d %d ",x,bel[x]); if(bel[x]==x) return x; return bel[x]=find(bel[x]); } void dijkstra() { memset(vis,0,sizeof(vis)); memset(val,48,sizeof(val)); val[1]=0; q.push(node(1,val[1])); while(!q.empty()) { node tmp = q.top(); q.pop(); if(vis[tmp.id]) continue; vis[tmp.id]=1; int x=tmp.id; for(int i=in[x];i;i=e[i].lt) { int y=e[i].to; if(val[y]>val[x]+e[i].v) val[y]=val[x]+e[i].v,q.push(node(y,val[y])); } } } bool cmp(edge x,edge y){return x.v>y.v;} int poi; int mn[N],f[N][18]; void kruskal() { //memset(bel,0,sizeof(bel)); sort(g+1,g+m+1,cmp); memset(mn,48,sizeof(mn)); memset(in,0,sizeof(in)); cnt=0; poi=n; for(int i=1;i<=m;i++) { int x=g[i].x,y=g[i].y; int fx=find(x),fy=find(y); if(fx==fy) continue; val[++poi]=g[i].v; tree(poi,fx); tree(poi,fy); bel[fx]=bel[fy]=poi; } } void dfs(int x) { vis[x]=1; for(int i=1;i<18;i++) f[x][i]=f[f[x][i-1]][i-1]; for(int i=in[x];i;i=t[i].lt) { int y=t[i].to; f[y][0]=x; dfs(y); mn[x]=min(mn[x],mn[y]); } if(x<=n) mn[x]=val[x]; } int getans(int x,int w) { for(int i=17;~i;i--) if(val[f[x][i]]>w) x=f[x][i]; //printf("%d ",val[x]); return mn[x]; } int main() { int T;scanf("%d",&T); while(T--) { memset(in,0,sizeof(in)); cnt=0; scanf("%d%d",&n,&m); int u,v,l,a; for(int i=1;i<=2*n;i++) bel[i]=i; for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&u,&v,&l,&a); add(u,v,l,a); } dijkstra(); kruskal(); memset(vis,0,sizeof(vis)); for(int i=1;i<2*n;i++) if(!vis[i]) dfs(find(i)); int Q,k,s,lastans=0,p; scanf("%d%d%d",&Q,&k,&s); val[0]=0; while(Q--) { scanf("%d%d",&v,&p); v=(v+k*lastans-1)%n+1; p=(p+k*lastans)%(s+1); printf("%d ",lastans=getans(v,p)); } } return 0; }