本文移植自个人的原博客（原文）

题目链接

题目描述

Rick and his co-workers have made a new radioactive formula and a lot of bad guys are after them. So Rick wants to give his legacy to Morty before bad guys catch them.

There are $n$ planets in their universe numbered from $1$ to $n$. Rick is in planet number $s$ (the earth) and he doesn’t know where Morty is. As we all know, Rick owns a portal gun. With this gun he can open one-way portal from a planet he is in to any other planet (including that planet). But there are limits on this gun because he’s still using its free trial.

By default he can not open any portal by this gun. There are $q$ plans in the website that sells these guns. Every time you purchase a plan you can only use it once but you can purchase it again if you want to use it more.

Plans on the website have three types:

With a plan of this type you can open a portal from planet $v$ to planet $u$.
With a plan of this type you can open a portal from planet $v$ to any planet with index in range $[l,r]$.
With a plan of this type you can open a portal from any planet with index in range $[l,r]$ to planet $v$.

Rick doesn’t known where Morty is, but Unity is going to inform him and he wants to be prepared for when he finds and start his journey immediately. So for each planet (including earth itself) he wants to know the minimum amount of money he needs to get from earth to that planet.

题解

线段树优化建图，对于向区间连边，可以将区间用线段树的节点表示出来，并从原节点向线段树中的节点建边，再对于线段树中长度为$1$的节点向原节点建边，跑最短路即可，注意对于区间向点建边的操作，需要另建一棵线段树，将上述操作反向进行，否则即默认任意节点之间存在一条长度为$0$的最短路。

using namespace std;
typedef long long ll;
const int N = 2e6+1;
const ll inf = 2e18;
int n,m,S,head[N*2],cnt,tot;

ll d[N*2];

struct nd{int ne,to;ll w;}e[N*2];

void in(int x,int y,ll w){e[++cnt].to=y;e[cnt].ne=head[x];head[x]=cnt;e[cnt].w=w;}

struct Segment_Tree
{
    int ls[N],rs[N],id[N],rt;
    int build(bool tp,int l,int r)
    {
        int x=++tot;
        if(l==r)
        {
            if(!tp)    in(x,l,0);
            else    in(l,x,0);
            return x;
        }
        int mid=l+r>>1;
        ls[x]=build(tp,l,mid);
        rs[x]=build(tp,mid+1,r);
//        cout<<ls[x]<<" "<<rs[x]<<endl;
        if(!tp)in(x,ls[x],0),in(x,rs[x],0);
        else in(ls[x],x,0),in(rs[x],x,0);
        return x;
    }

    void change(int fr,int L,int R,ll d,bool tag,int x,int l,int r)
    {
        if(L<=l&&r<=R)
        {
//            cout<<x<<" "<<l<<" "<<r<<endl;
            if(!tag)in(fr,x,d);
            else    in(x,fr,d);
            return;
        }
        int mid=l+r>>1;
        if(L<=mid)change(fr,L,R,d,tag,ls[x],l,mid);
        if(R>mid)change(fr,L,R,d,tag,rs[x],mid+1,r);
        return;
    }

    void init(bool tp){rt=build(tp,1,n);}
}t1,t2;
bool inq[N*2];
void spfa(int s)
{
    queue<int>q;q.push(s);
    for(int i=1;i<=tot;++i)d[i]=inf;
    d[s]=0;inq[s]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();inq[x]=0;
        for(int i=head[x];i;i=e[i].ne)
        {
            int y=e[i].to;
            if(d[y]>d[x]+e[i].w)
            {
                d[y]=d[x]+e[i].w;
                if(!inq[y])q.push(y),inq[y]=1;
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&S);
    tot=n;
    t1.init(1);
    t2.init(0);
    for(int i=1,tp,x,y,l,r,w;i<=m;++i)
    {
        scanf("%d",&tp);
        if(tp==1)
        {
            scanf("%d%d%d",&x,&y,&w);
            in(x,y,w);
        }
        if(tp==2)
        {
            scanf("%d%d%d%d",&x,&l,&r,&w);
            t2.change(x,l,r,w,0,t2.rt,1,n);
        }
        if(tp==3)
        {
            scanf("%d%d%d%d",&y,&l,&r,&w);
            t1.change(y,l,r,w,1,t1.rt,1,n);
        }
    }
    spfa(S);
    for(int i=1;i<=n;++i)
    printf("%I64d ",(d[i]==inf?-1:d[i]));
}
/*
3 1 1
2 1 2 3 1
*/

Codeforces787D Legacy

题目链接

题目描述

题解