Legacy

CF786B

题意：

一张图上有 n 个点，现在做 m 次操作，操作总共有 3 种：

• 1 a b c： 从 a 到 b 连一条权值为 c 的单向边。(t=1)
• 2 a b c d：从 a 到 [b, c]中的每个点都连一条权值为 d 的单向边。(t=2)
• 3 a b c d：从 [b, c]中的每个点都往 a 连一条权值为 d 的单向边。(t=3)
• 最后给你一个起点 s

分析：

• n比较大，并且有区间建边的操作，抛弃 建边的思想。
• 那就通过数据结构实现区间建边。假设我们从 1 号点往 [2, 9] 中的点连边。我们需要线段树建一棵树，每个点可以到达它的两个子节点。
  
  因为是单向边，所以得建两棵树，然后跑一遍DJ

代码

//暴力连边会炸,考虑区间连边
#include<bits/stdc++.h>

#define fir first
#define sec second
#define ls now<<1
#define rs now<<1|1

#define ll long long

using namespace std;

const int N=2e6+10;

int n,m,s,cnt,tot;
int id[2][N],ver[N],nex[N],h[N];

ll dis[N],pri[N];

priority_queue<pair<ll,int > > q;

inline void adk(int x,int y,ll z)
{
    nex[tot]=h[x];
    ver[tot]=y;
    pri[tot]=z;
    h[x]=tot++;
}

inline void add(int x,int y,int z,int f)
{
    if(f==0) adk(x,y,z);
    else adk(y,x,z);
}

inline void build(int now,int l,int r,int f)
{
    if(l==r)
    {
        id[f][now]=l;
        return ;
    }

    id[f][now]=++cnt;
    int mid=(l+r)>>1;
    build(ls,l,mid,f);build(rs,mid+1,r,f);
    add(id[f][now],id[f][ls],0,f);
    add(id[f][now],id[f][rs],0,f);//父连子 
}

inline void nect(int now,int l,int r,int v,int x,int y,ll z,int f)
{
    if(l>=x&&r<=y)
    {
        add(v,id[f][now],z,f);
        return ;
    }

    int mid=(l+r)>>1;
    if(x<=mid) nect(ls,l,mid,v,x,y,z,f);
    if(mid<y) nect(rs,mid+1,r,v,x,y,z,f);
}

int main()
{
    memset(h,-1,sizeof(h));
    scanf("%d%d%d",&n,&m,&s);

    cnt=n;
    build(1,1,n,0);
    build(1,1,n,1);

    int op,x,l,r;ll w;
    while(m--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%lld",&l,&r,&w);
            nect(1,1,n,l,r,r,w,0);
        }
        else
        {
            scanf("%d%d%d%lld",&x,&l,&r,&w);
            nect(1,1,n,x,l,r,w,op-2);
        }
    }

    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        int k=q.top().sec;q.pop();
        for (int i=h[k];~i;i=nex[i])
        {
            int j=ver[i];
            if(dis[j]>dis[k]+pri[i])
            {
                dis[j]=dis[k]+pri[i];
                q.push(make_pair(-dis[j],j));
            }
        }
    }

    for (int i=1;i<=n;i++)
        printf("%lld ",(dis[i]>1e16 ? -1:dis[i]));

    return 0;
}