题目链接：codeforces787D.Legacy

题意：

给有向带权图，然后在其中加边，有三种操作：

1. u->v加一条权值为w的边。
2. [l,r]->v加(r-l+1)条权值为w的边。
3. u->[l,r]加(r-l+1)条权值为w的边。

然后询问以s点为起点到其他所有点的最短路。

题解：

线段树优化建图。

考虑建两棵线段树A，B，然后：

1. A线段树的每个非叶子节点的儿子向该节点连权值为0的边。
2. B线段树的每个非叶子节点向该节点的儿子连权值为0的边。
3. B线段树的每个叶子节点向A线段树对应的叶子节点连权值为0的边。

这其中A线段树的叶子节点就代表原图中的节点，其余节点都是用来优化建图的。

对于加边的操作：

1. 建立虚点p1,p2。
2. A线段树上的区间[l,r]向p1连权值为0的边。
3. p1向p2连权值为w的边。
4. p2向B线段树上的区间[l,r]连权值为0的边。

最后跑dijkstra即可，注意dijkstra中向堆中加点的操作有变化。

PS.数组尽量往大的开QAQ。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=0x7f7f7f7f7f7f7f7f;
const int MAXN=1e5+9;
const int MAXM=1e5+9;
int n,m,s;
int rta,rtb,tot;
int ls[MAXN<<5],rs[MAXN<<5];
int V[MAXN<<5];
struct Edge
{
    int v,nxt;
    ll w;
} edge[MAXN<<5];
int cnt=0,fir[MAXN<<5];
void addedge(int u,int v,ll w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].nxt=fir[u];
    fir[u]=cnt++;
}
void build(int l,int r,int &rt,bool flag)
{
    rt=++tot;
    if(l==r)
    {
        if(flag)
            V[l]=rt;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls[rt],flag);
    build(mid+1,r,rs[rt],flag);
    if(flag)
    {
        addedge(ls[rt],rt,0);
        addedge(rs[rt],rt,0);
    }
    else
    {
        addedge(rt,ls[rt],0);
        addedge(rt,rs[rt],0);
    }
}
void deal(int l,int r,int leafA,int leafB)
{
    if(l==r)
    {
        addedge(leafB,leafA,0);
        return;
    }
    int mid=(l+r)>>1;
    deal(l,mid,ls[leafA],ls[leafB]);
    deal(mid+1,r,rs[leafA],rs[leafB]);
}
void update(int L,int R,int p,int l,int r,int rt,bool flag)
{
    if(L<=l&&r<=R)
    {
        if(flag)
            addedge(rt,p,0);
        else
            addedge(p,rt,0);
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid)
        update(L,R,p,l,mid,ls[rt],flag);
    if(R>mid)
        update(L,R,p,mid+1,r,rs[rt],flag);
}
void link(int a,int b,int c,int d,ll w)
{
    update(a,b,++tot,1,n,rta,1);
    addedge(tot,tot+1,w);
    update(c,d,++tot,1,n,rtb,0);
}
ll dis[MAXN<<5];
bool used[MAXN<<5];
void dijkstra(int st)
{
    priority_queue<pair<ll, int> > q;
    while(!q.empty())
        q.pop();
    memset(dis,INF,sizeof(dis));
    dis[st]=0;
    q.push(make_pair(0,st));
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        if(used[u])
            continue;
        used[u]=1;
        for(int i=fir[u];i!=-1;i=edge[i].nxt)
        {
            int v=edge[i].v;
            ll w=edge[i].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                q.push(make_pair(-dis[v],v));
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    memset(fir,-1,sizeof(fir));
    build(1,n,rta,1);
    build(1,n,rtb,0);
    deal(1,n,rta,rtb);
    for(int i=1; i<=m; i++)
    {
        int op,u,w,l,r;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&u,&l,&w);
            link(u,u,l,l,w);
        }
        else    if(op==2)
        {
            scanf("%d%d%d%d",&u,&l,&r,&w);
            link(u,u,l,r,w);
        }
        else
        {
            scanf("%d%d%d%d",&u,&l,&r,&w);
            link(l,r,u,u,w);
        }
    }
    dijkstra(V[s]);
    for(int i=1; i<=n; i++)
        if(dis[V[i]]!=INF)
            printf("%lld ",dis[V[i]]);
        else
            printf("-1 ");
    return 0;
}