CF786B Legacy

蔚落 2022-10-02 14:49 155阅读 0赞

线段树优化建图！

板子题吧

就是入树是上连下 原因是到达可以从父亲节点走到下面

然后出树是下连上 原因是可以进来以后再走到父亲节点再出发

具体建图可以看代码啦

就是建好了以后直接跑spfa就好啦【可能在国外spfa还没死。。。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//Love and Freedom.
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<queue>
    #define ll long long
    #define inf 2002122520021225ll
    #define N 400010
    #define ls (x<<1)
    #define rs (x<<1|1)
    #define fa (x>>1)
    #define mid (l+r>>1)
    using namespace std;
    
    queue<int> que;
    struct edge{
         int to,lt,v;}e[N*20];
    int tot,in[N<<2],cnt,s,n,m;ll dis[N<<2],pos[N][2];
    void add(int x,int y,int v){e[++cnt].to=y; e[cnt].lt=in[x]; in[x]=cnt; e[cnt].v=v;}
    struct sgt
    {
        int id[N<<1][2]; // 0 in 1 out
        void build(int x,int l,int r)
        {
            id[x][0]=++tot; id[x][1]=++tot;
            if(l==r)
            {
                pos[l][0]=id[x][0]; pos[l][1]=id[x][1];
                add(id[x][0],id[x][1],0),add(id[x][1],id[x][0],0);
                return;
            }
            build(ls,l,mid); build(rs,mid+1,r);
            add(id[x][0],id[ls][0],0); add(id[ls][1],id[x][1],0);
            add(id[x][0],id[rs][0],0); add(id[rs][1],id[x][1],0);
        }
        void link(int x,int l,int r,int LL,int RR,int poi,int v,int typ)
        {
            if(LL<=l && RR>=r)
            {
                if(!typ)    add(id[x][1],poi,v);
                else    add(poi,id[x][0],v);
                return;
            }
            if(LL<=mid)    link(ls,l,mid,LL,RR,poi,v,typ);
            if(RR>mid)    link(rs,mid+1,r,LL,RR,poi,v,typ);
        }
    }sgt;
    void spfa()
    {
        for(int i=1;i<=tot;i++)    dis[i]=inf;
        dis[s]=0; que.push(s);
        while(!que.empty())
        {
            int x=que.front(); que.pop();
            for(int i=in[x];i;i=e[i].lt)
            {
                int y=e[i].to;
                if(dis[x]+e[i].v<dis[y])
                {
                    dis[y]=dis[x]+e[i].v;
                    que.push(y);
                }
            }
        }
    }
    int main()
    {
        int typ,x,l,r,y,v;
        scanf("%d%d%d",&n,&m,&s); sgt.build(1,1,n);
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&typ);
            if(typ==1)
                scanf("%d%d%d",&x,&y,&v),add(pos[x][0],pos[y][1],v);
            else if(typ==2)
                scanf("%d%d%d%d",&x,&l,&r,&v),sgt.link(1,1,n,l,r,pos[x][1],v,1);
            else
                scanf("%d%d%d%d",&x,&l,&r,&v),sgt.link(1,1,n,l,r,pos[x][0],v,0);
        }
        s=pos[s][0]; spfa();
        for(int i=1;i<=n;i++)
            printf("%I64d ",dis[pos[i][1]]==inf?-1:dis[pos[i][1]]);
        return 0;
    }

转载于:https://www.cnblogs.com/hanyuweining/p/11062465.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/33e476d1bef34206b94c5a796f60e6f6.png