今天也要踏上归程了呢~（题外话
kruskal重构树！当时就听学长们说过是重构树辣所以做起来也很快233
就是我们按照a建最大生成树 这样话呢我们就可以通过生成树走到尽量多的点啦
然后呢就是从这个子树内走到1的最短路 提前处理出来然后就是子树最小值啦w
附代码。（些许丑陋（
//Love and Freedom.#include#include #include #include #include #define ll long long#define inf 20021225#define N 400010#define M 800010using 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 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\n",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\n",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\n",lastans=getans(v,p)); } } return 0;}