NOI Day1T1归程(Kruskal重构树+Dijkstra)

题目

洛谷题目传送门

题解

其实我不想写......，所以......

挖个坑......我以后一定会补的

luogu的题解讲的还是很详细的......

恩，感谢cwen详细教我做这道题，让我2遍A

然后我丑陋的代码(代码太长，所以压得很丑)

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iomanip>

#include<algorithm>

#include<ctime>

#include<queue>

#include<stack>

#include<vector>

#define rg register

#define il inline

#define lst long long

#define ldb long double

#define N 400050

#define M 800050

using namespace std;

const lst Inf=1e16;

il int read()

{

    rg int s=0,m=0;rg char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}

    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();

    return m?-s:s;

}

int n,m,Q,K,S,u,p;

int cnt,tot;

lst ans;

int hd[N],fa[N];

lst dis[N],tr_dis[N];

lst f[N][25],g[N][25];

struct WAY{int u,v;lst w,h;}edge[M];

struct EDGE{int to,nxt;lst v,h;}ljl[M<<1];

il int operator<(rg const WAY &a,rg const WAY &b){return a.h>b.h;}

il void memt()

{

    cnt=0;

    memset(hd,0,sizeof(hd));

    memset(ljl,0,sizeof(ljl));

}

il void add(rg int p,rg int q,rg int o,rg int hi){ljl[++cnt]=(EDGE){q,hd[p],o,hi},hd[p]=cnt;}

int vis[N];

struct hh{lst D;int id;};

bool operator<(rg const hh &a,rg const hh &b){return a.D>b.D;}

priority_queue <hh> H;

il void Dijkstra()

{

    for(rg int i=1;i<=n;++i)vis[i]=0,dis[i]=Inf;

    dis[1]=0,H.push((hh){0,1});

    while(!H.empty())

    {

        rg hh S=H.top();H.pop();

        rg int now=S.id;

        if(vis[now])continue;

        vis[now]=1;

        for(rg int i=hd[now];i;i=ljl[i].nxt)

        {

            rg int qw=ljl[i].to;

            if(dis[qw]>dis[now]+ljl[i].v)

            {

                dis[qw]=dis[now]+ljl[i].v;

                H.push((hh){dis[qw],qw});

            }

        }

    }

}

int find_fa(rg int now)

{

    if(fa[now]==now)return now;

    return fa[now]=find_fa(fa[now]);

}

il void Kruskal()

{

    rg int nn=2*n;tot=n;

    for(rg int i=1;i<=nn;++i)fa[i]=i;

    sort(edge+1,edge+m+1);

    for(rg int i=1;i<=m;++i)

    {

        rg int u=edge[i].u,v=edge[i].v;

        rg int fx=find_fa(u),fy=find_fa(v);

        if(fx!=fy)

        {

            tot++;

            add(tot,fx,0,edge[i].h);

            add(tot,fy,0,edge[i].h);

            fa[fx]=fa[fy]=tot;

            if(tot==nn-1)break;

        }

    }

}

void dfs(rg int now,rg int fm,rg lst up)

{

    f[now][0]=fm,g[now][0]=up;

    for(rg int j=1;j<=20;++j)

    {

        f[now][j]=f[f[now][j-1]][j-1];

        g[now][j]=min(g[now][j-1],g[f[now][j-1]][j-1]);

    }

    for(rg int i=hd[now];i;i=ljl[i].nxt)

    {

        rg int qw=ljl[i].to;

        if(qw!=fm)

            dfs(qw,now,ljl[i].h);

        tr_dis[now]=min(tr_dis[qw],tr_dis[now]);

    }

}

int main()

{

    for(rg int T=read();T;T--)

    {

        memt();

        n=read(),m=read();

        for(rg int i=1;i<=m;++i)

        {

            rg int p=read(),q=read(),o=read(),hi=read();

            add(p,q,o,hi),add(q,p,o,hi);

            edge[i]=(WAY){p,q,o,hi};

        }

        Dijkstra(),memt();

        Kruskal();

        for(rg int i=1;i<=n;++i)tr_dis[i]=dis[i];

        for(rg int i=n+1;i<=tot;++i)tr_dis[i]=Inf;

        dfs(tot,0,0);

        ans=0;

        Q=read(),K=read(),S=read();

        while(Q--)

        {

            u=read(),p=read();

            u=(u+K*ans-1)%n+1;

            p=(p+K*ans)%(S+1);

            for(rg int j=19;j>=0;--j)

                if(g[u][j]>p)u=f[u][j];

            ans=tr_dis[u];

            printf("%lld\n",ans);

        }

    }

    return 0;

}