Legacy

裸的线段树优化连边,怎么来理解??

比如,怎么让一个点向一个区间连边??

这个时候新建一颗线段树,线段树上的点都是虚点

当点连向区间时

就把点连向线段树上完全覆盖的节点

然后线段树上,父节点向儿子连费用零的边,叶子节点向对应的实点连边

这样一来,就可以经过线段树的周转以费用零的代价来到另一个实点.

但是还要解决区间向点连边

那不妨再开一棵线段树,这次由实点向叶子节点连边,线段树上儿子向父亲连费用零的边

#include <bits/stdc++.h>
using namespace std;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
typedef long long ll;
const int maxn = 2e6+10;
const ll inf = 1e18;
struct edge{
    int to,nxt; ll w;
}d[maxn<<1]; int head[maxn<<1],cnt=1,id,n,Q,s;
void add(int u,int v,ll w)
    { d[++cnt]=(edge){v,head[u],w},head[u]=cnt; }
void build1(int rt,int l,int r)
{
    id = max( id,rt );
    if( l==r ){ add(rt+n,l,0); return; }    //叶子节点连向真实节点 
    build1(lson); build1(rson);
    add( rt+n,ls+n,0 );    add( rt+n,rs+n,0 );    //向儿子连边 
}
void build2(int rt,int l,int r)
{
    if( l==r ){ add(l,rt+n+id,0); return; }
    build2(lson); build2(rson);
    add( ls+n+id,rt+n+id,0 ); add(rs+n+id,rt+n+id,0 );//向父亲连边 
}
void run1(int rt,int l,int r,int u,int L,int R,ll val)
{
    if( r<L||l>R )    return;
    if( L<=l&&R>=r )
    {
        add(u,rt+n,val);
        return;
    }
    run1(lson,u,L,R,val); run1(rson,u,L,R,val);
}
void run2(int rt,int l,int r,int L,int R,int u,ll val)
{
    if( r<L||l>R )    return;
    if( L<=l&&R>=r )
    {
        add(rt+n+id,u,val);
        return;
    }
    run2(lson,L,R,u,val); run2(rson,L,R,u,val);
}
typedef pair<ll,int>p;
priority_queue<p,vector<p>,greater<p> >q;
ll dis[maxn];
int vis[maxn];
void dij(int s)
{
    for(int i=0;i<=2e6;i++)    dis[i]=inf;
    dis[s]=0,q.push(p(0,s));
    while(!q.empty())
    {
        p now=q.top();q.pop();
        int num=now.second;
        if(vis[num])    continue;
        vis[num]=1;
        for(int i=head[num];i;i=d[i].nxt)
        {
            if(dis[d[i].to]>dis[num]+d[i].w)
            {
                dis[d[i].to]=dis[num]+d[i].w;
                q.push(p(dis[d[i].to],d[i].to));
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&Q,&s);
    id = n;
    build1(1,1,n); build2(1,1,n);
    while( Q-- )
    {
        int type; ll u,l,r,w;
        scanf("%d",&type);
        if( type==1 )
        {
            scanf("%lld%lld%lld",&l,&r,&w);
            if( l!=r )    add(l,r,w);
        }
        else if( type==2 )
        {
            scanf("%lld%lld%lld%lld",&u,&l,&r,&w);
            run1(1,1,n,u,l,r,w);
        }
        else if( type==3 )
        {
            scanf("%lld%lld%lld%lld",&u,&l,&r,&w);
            run2(1,1,n,l,r,u,w);
        }
    }
    dij(s);
    for(int i=1;i<=n;i++)
        printf("%lld\n",( dis[i] < inf ? dis[i]:-1 ) );
}