100pts
```cpp
#include<bits/stdc++.h>
#define maxn 2000010
using namespace std;
int head[maxn],tot;//用于求最短路
int tree_head[maxn],sum;//用于重构树
int n,m;
int f[maxn],fa[maxn][25],dif[maxn];
struct Edge{
int u,v,len,height,next;
void add(int x,int y,int l,int h){u=x,v=y,len=l,height=h;}
void add_edge(int x,int y,int l,int h){
u=x,v=y,len=l,height=h;
next=head[u];
head[u]=tot;
}
// void _add(int x,int y){
// v=y;
// next=tree_head[u];
// tree_head[u]=sum;
// printf("%d\n",tree_head[u]);
// printf("%d to %d",x,y);
// printf("all right\n");
// }
bool operator <(Edge path)const{
return path.height <height;
}
};
Edge e[maxn];//用于求最短路
Edge E[maxn];//用于构建Kruskal树
Edge ed[maxn];//用于存储输入数据
struct node{
int pos,dis;
bool operator <(node nd)const {
return dis>nd.dis ;
}
};
priority_queue<node >q;
bool vis[maxn];
int dis[maxn];
void dijkstra(){
dis[1]=0;
q.push((node){1,0});
while(!q.empty()){
node now=q.top();
q.pop();
int u=now.pos ;
if(vis[u])continue;
vis[u]=true;
for(int i=head[u];i;i=e[i].next ){
int v=e[i].v ;
if(dis[v]>dis[u]+e[i].len){
dis[v]=dis[u]+e[i].len ;
if(!vis[v])q.push((node){v,dis[v]});
}
}
}
}
void _add(int x,int y){
E[++sum].v =y;
E[sum].next =tree_head[x];
tree_head[x]=sum;
}
void dfs(int u){
//printf("now is %d\n",u);
for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
//if(!tree_head[u])return ;
for(int i=tree_head[u];i;i=E[i].next ){
int v=E[i].v ;
dfs(v);
//printf("%d\n",dis[v]);
dis[u]=min(dis[u],dis[v]);
}
return ;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int num;
void kruskal(){
for(int i=1;i<=n;i++)f[i]=i;
sort(ed+1,ed+m+1);
int cnt=n;
for(int i=1;i<=m;i++){
int u=ed[i].u ,v=ed[i].v ;
int fu=find(u),fv=find(v);
if(fu==fv)continue;
dif[++cnt]=ed[i].height;
f[fu]=f[fv]=f[cnt]=cnt;
fa[fu][0]=fa[fv][0]=cnt;
// E[++sum]._add(cnt,fu);
// E[++sum]._add(cnt,fv);
_add(cnt,fu);
_add(cnt,fv);
}
// num=cnt;
// for(int i=1;i<=num;i++)printf("%d ",tree_head[i]);
// printf("\n");
dfs(cnt);
// for(int i=1;i<=cnt;i++)printf("%d ",dis[i]);
// printf("\n");
}
int main(){
int T;
scanf("%d",&T);
for(int up=1;up<=T;up++){
memset(e,0,sizeof e);
memset(ed,0,sizeof ed);
memset(E,0,sizeof E);
memset(vis,0,sizeof vis);
memset(tree_head,0,sizeof tree_head);
memset(head,0,sizeof head);
//f,fa,dif
memset(f,0,sizeof f);
memset(fa,0,sizeof fa);
memset(dif,0,sizeof dif);
scanf("%d%d",&n,&m);
for(int i=1,u,v,l,a;i<=m;i++){
scanf("%d%d%d%d",&u,&v,&l,&a);
ed[i].add(u,v,l,a);
e[++tot].add_edge(u,v,l,a);
e[++tot].add_edge(v,u,l,a);
}
//for(int i=1;i<=100;i++)dis[i]=10000;
memset(dis,0x3f3f3f3f,sizeof dis);
dijkstra();
// dfs(num);
kruskal();
// for(int i=1;i<=num;i++)printf("%d ",dis[i]);
// printf("\n");
int q,k,s,lastans=0;
scanf("%d%d%d",&q,&k,&s);
for(int i=1,v,p;i<=q;i++){
scanf("%d%d",&v,&p);
v=(v+k*lastans-1)%n+1;
p=(p+k*lastans)%(s+1);
for(int i=20;i>=0;i--){
if(fa[v][i]&&dif[fa[v][i]]>p)v=fa[v][i];
}
printf("%d\n",dis[v]);
lastans=dis[v];
}}
return 0;
}
```
还有，为什么数组要开到160w啊？不应该2m=80w就行了吗？而且我开160w还会re，必须开到200w
by HRLYB @ 2019-08-27 16:40:27