题解 CF786B 【Legacy】

本题要求我们支持三种操作：

① 点向点连边。 ② 点向区间连边。 ③ 区间向点连边。

然后跑最短路得出答案。

考虑使用线段树优化建图。

建两颗线段树，入树和出树，每个节点为一段区间的原节点集合。入树内部为儿子向父亲连有向边，出树内部为父亲连有向边，因为入树和出树的叶子节点都为原图中的点，所以两棵树的对应叶子节点连无向边，这些边边权都为\(0\)。

示意图如下，左边为入树，右边为出树。

操作一时，从入树叶子节点向出树叶子节点连边（红色的线）。

操作二时，从入树叶子节点向出树所对应的区间节点连边（蓝色的线）。

操作三时，从入树所对应的区间节点向出树叶子节点连边（绿色的线）。

具体实现细节看代码吧。

记得开\(long\ long\)和开大数组。

\(code:\)

#include<bits/stdc++.h>

#define maxn 800010

#define inf 2000000000

using namespace std;

typedef long long ll;

template<typename T> inline void read(T &x)

{

	x=0;char c=getchar();bool flag=false;

	while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

	if(flag)x=-x;

}

int n,m,s,flag;

struct edge

{

    int to,nxt,v;

}e[maxn];

int head[maxn],edge_cnt;

void add(int from,int to,int val)

{

    e[++edge_cnt]=(edge){to,head[from],val};

    head[from]=edge_cnt;

}

int in_root,out_root,tree_cnt;

int ls[maxn],rs[maxn],in_num[maxn],out_num[maxn];

void build_in(int L,int R,int &cur)

{

    cur=++tree_cnt;

    if(L==R)

    {

        in_num[L]=cur;

        return;

    }

    int mid=(L+R)>>1;

    build_in(L,mid,ls[cur]);

    build_in(mid+1,R,rs[cur]);

    add(ls[cur],cur,0),add(rs[cur],cur,0);

}

void build_out(int L,int R,int &cur)

{

    cur=++tree_cnt;

    if(L==R)

    {

        out_num[L]=cur;

        return;

    }

    int mid=(L+R)>>1;

    build_out(L,mid,ls[cur]);

    build_out(mid+1,R,rs[cur]);

    add(cur,ls[cur],0),add(cur,rs[cur],0);

}

void modify_in(int L,int R,int l,int r,int pos,int val,int &cur)

{

    if(L<=l&&R>=r)

    {

        add(cur,pos,val);

        return;

    }

    int mid=(l+r)>>1;

    if(L<=mid) modify_in(L,R,l,mid,pos,val,ls[cur]);

    if(R>mid) modify_in(L,R,mid+1,r,pos,val,rs[cur]);

}

void modify_out(int L,int R,int l,int r,int pos,int val,int &cur)

{

    if(L<=l&&R>=r)

    {

        add(pos,cur,val);

        return;

    }

    int mid=(l+r)>>1;

    if(L<=mid) modify_out(L,R,l,mid,pos,val,ls[cur]);

    if(R>mid) modify_out(L,R,mid+1,r,pos,val,rs[cur]);

}

ll dis[maxn];

bool vis[maxn];

struct node

{

    ll val;

    int num;

};

bool operator <(const node &x,const node &y)

{

    return x.val>y.val;

}

priority_queue<node> q;

void dijkstra()

{

    s=in_num[s];

    for(int i=1;i<=tree_cnt;++i) dis[i]=inf;

    dis[s]=0;

    q.push((node){0,s});

    while(!q.empty())

    {

        node tmp=q.top();

        q.pop();

        int x=tmp.num;

        if(vis[x]) continue;

        vis[x]=true;

        for(int i=head[x];i;i=e[i].nxt)

        {

            int y=e[i].to,v=e[i].v;

            if(dis[y]>dis[x]+v)

            {

                dis[y]=dis[x]+v;

                q.push((node){dis[y],y});

            }

        }

    }

}

int main()

{

	read(n),read(m),read(s);

    build_in(1,n,in_root);

    build_out(1,n,out_root);

    for(int i=1;i<=n;++i)

        add(in_num[i],out_num[i],0),add(out_num[i],in_num[i],0);

    while(m--)

    {

        read(flag);

        int x,y,l,r,v;

        if(flag==1)

        {

            read(x),read(y),read(v);

            add(in_num[x],out_num[y],v);

        }

        if(flag==2)

        {

            read(x),read(l),read(r),read(v);

            modify_out(l,r,1,n,in_num[x],v,out_root);

        }

        if(flag==3)

        {

            read(x),read(l),read(r),read(v);

            modify_in(l,r,1,n,out_num[x],v,in_root);

        }

    }

    dijkstra();

    for(int i=1;i<=n;++i)

    {

        if(dis[out_num[i]]==inf) printf("-1 ");

        else printf("%lld ",dis[out_num[i]]);

    }

	return 0;

}

巴特西

题解 CF786B 【Legacy】

最新文章

热门文章