BZOJ5415[Noi2018]归程——kruskal重构树+倍增+堆优化dijkstra

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
typedef pair<int,int> pr;
int ans;
int tot;
int cnt;
int num;
int n,m;
int T,t;
int k,S;
int x,y,z,w;
int f[1600010];
int d[1600010];
int v[1600010];
int ls[1600010];
int rs[1600010];
int mn[1600010];
int to[1600010];
int fa[1600010];
int vis[1600010];
int val[1600010];
int head[1600010];
int next[1600010];
int g[1600010][21];
int INF=2147483647;
struct node
{
    int u;
    int v;
    int s;
}a[1600010],b[1600010];
void add(int x,int y,int z)
{
    tot++;
    next[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
    val[tot]=z;
}
int get(int x)
{
    if(fa[x]==x)
    {
        return x;
    }
    return fa[x]=get(fa[x]);
}
int find(int x)
{
    if(f[x]==x)
    {
        return x;
    }
    return f[x]=find(f[x]);
}
bool cmp(node a,node b)
{
    return a.s>b.s;
}
void dijkstra(int st)
{
    priority_queue< pr,vector<pr>,greater<pr> >q;
    for(int i=1;i<=n;i++)
    {
        d[i]=INF;
    }
    d[st]=0;
    q.push(make_pair(d[st],st));
    while(!q.empty())
    {
        int now=q.top().second;
        q.pop();
        if(vis[now])
        {
            continue;
        }
        vis[now]=1;
        for(int i=head[now];i;i=next[i])
        {
            if(d[to[i]]>d[now]+val[i])
            {
                d[to[i]]=d[now]+val[i];
                q.push(make_pair(d[to[i]],to[i]));
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        mn[i]=d[i];
    }
}
void dfs(int x)
{
    int res=INF;
    for(int i=1;i<=20;i++)
    {
        g[x][i]=g[g[x][i-1]][i-1];
    }
    if(x<=n)
    {
        return ;
    }
    if(ls[x])
    {
        dfs(ls[x]);
        res=min(res,mn[ls[x]]);
    }
    if(rs[x])
    {
        dfs(rs[x]);
        res=min(res,mn[rs[x]]);
    }
    mn[x]=res;
    return ;
}
int ST(int x,int mx)
{
    for(int i=20;i>=0;i--)
    {
        if(v[g[x][i]]>mx)
        {
            x=g[x][i];
        }
    }
    return x;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        cnt=0;
        num=0;
        tot=0;
        ans=0;
        memset(head,0,sizeof(head));
        memset(mn,0,sizeof(mn));
        memset(v,0,sizeof(v));
        memset(ls,0,sizeof(ls));
        memset(rs,0,sizeof(rs));
        memset(g,0,sizeof(g));
        memset(vis,0,sizeof(vis));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d%d",&x,&y,&z,&w);
            add(x,y,z);
            add(y,x,z);
            a[i].u=x;
            a[i].v=y;
            a[i].s=w;
        }
        dijkstra(1);
        for(int i=1;i<=n;i++)
        {
            fa[i]=i;
        }
        for(int i=1;i<=n*2;i++)
        {
            f[i]=i;
        }
        sort(a+1,a+1+m,cmp);
        for(int i=1;i<=m;i++)
        {
            int fx=get(a[i].u);
            int fy=get(a[i].v);
            if(fx!=fy)
            {
                b[++num].u=a[i].u;
                b[num].v=a[i].v;
                b[num].s=a[i].s;
                fa[fx]=fy;
                if(num==n-1)
                {
                    break;
                }
            }
        }
        cnt=n;
        for(int i=1;i<=num;i++)
        {
            int fx=find(b[i].u);
            int fy=find(b[i].v);
            cnt++;
            f[fx]=cnt;
            f[fy]=cnt;
            ls[cnt]=fx;
            rs[cnt]=fy;
            g[fx][0]=cnt;
            g[fy][0]=cnt;
            v[cnt]=b[i].s;
        }
        dfs(cnt);
        scanf("%d%d%d",&t,&k,&S);
        while(t--)
        {
            scanf("%d%d",&x,&y);
            x=(x+k*ans-1)%n+1;
            y=(y+k*ans)%(S+1);
            ans=mn[ST(x,y)];
            printf("%d\n",ans);
        }
    }
}