Codeforces787D

Description

\(n(n\leq10^5)\)个点构成的有向图，有\(m(m\leq10^5)\)条连通信息，信息有三种：

1 u v w，表示存在一条边权为\(w\)的有向边\((u,v)\)；
2 u L R w，表示\(\forall v\in[L,R]\)，存在一条边权为\(w\)的有向边\((u,v)\)；
3 u L R w，表示\(\forall v\in[L,R]\)，存在一条边权为\(w\)的有向边\((v,u)\)。

其中\(w\leq10^9\)。求点\(s\)到每个点的最短路，不存在输出\(-1\)。

Solution

线段树优化建图。

建立两棵线段树，其上点的点权分别表示“到达这个区间内所有点的最小花费”和“到达这个区间内任意一个点的最小花费”。

第一棵线段树上，由于花费\(v_{[L,R]}\)能够到达\([L,R]\)中所有点，当然也包含\([L,mid]\)和\([mid+1,R]\)，所以父节点向子节点连0边；第二棵线段树上，由于花费\(v_{[L,R]}\)能够到达\([L,R]\)中的一个点，这个点当然也包含在其父节点中，所以子节点向父节点连0边。

如果不做感性理解的话，两棵线段树上的点分别用于连和被连，连向第一棵树上的\([L,R]\)就等价于连向\([L,R]\)中的每一个点，被第二棵树上的\([L,R]\)连就等价于被\([L,R]\)中的每一个点连。

由于每一条信息最多建立\(O(logn)\)条边，所以总边数是\(O(mlogn+4n)\)。

建完图后直接跑一遍单源最短路就好啦。

Code

//Legacy

#include <cstdio>

#include <cstring>

#include <queue>

typedef long long lint;

inline char gc()

{

    static char now[1<<16],*s,*t;

    if(s==t) {t=(s=now)+fread(now,1,1<<16,stdin); if(s==t) return EOF;}

    return *s++;

}

inline int read()

{

    int x=0; char ch=gc();

    while(ch<'0'||'9'<ch) ch=gc();

    while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();

    return x;

}

inline int min(int x,int y) {return x<y?x:y;}

const int N=1e5+10;

int n,m,s;

const int N1=3e5+110;

int cnt,rt1,rt2,ch[N1][2];

int h[N1],edCnt;

struct edge{int v,w,nxt;} ed[N*20];

inline void edAdd(int u,int v,int w)

{

    edCnt++; ed[edCnt].v=v,ed[edCnt].w=w;

    ed[edCnt].nxt=h[u],h[u]=edCnt;

}

void bldTr1(int &p,int L0,int R0)

{

    if(L0==R0) {p=L0; return;}

    p=++cnt;

    int mid=L0+R0>>1;

    bldTr1(ch[p][0],L0,mid);

    bldTr1(ch[p][1],mid+1,R0);

    edAdd(p,ch[p][0],0),edAdd(p,ch[p][1],0);

}

void bldTr2(int &p,int L0,int R0)

{

    if(L0==R0) {p=L0; return;}

    p=++cnt;

    int mid=L0+R0>>1;

    bldTr2(ch[p][0],L0,mid);

    bldTr2(ch[p][1],mid+1,R0);

    edAdd(ch[p][0],p,0),edAdd(ch[p][1],p,0);

}

int optL,optR;

void add(int p,int L0,int R0,int u,int w,int type)

{

    if(optL<=L0&&R0<=optR)

    {

        if(type==2) edAdd(u,p,w); else edAdd(p,u,w);

        return;

    }

    int mid=L0+R0>>1;

    if(optL<=mid) add(ch[p][0],L0,mid,u,w,type);

    if(mid<optR) add(ch[p][1],mid+1,R0,u,w,type);

}

const lint INF=0x3F3F3F3F3F3F3F3F;

lint dst[N1];

std::queue<int> Q;

void SPFA(int s)

{

    memset(dst,0x3F,sizeof dst);

    dst[s]=0; Q.push(s);

    while(!Q.empty())

    {

        int u=Q.front(); Q.pop();

        for(int i=h[u];i;i=ed[i].nxt)

        {

            int v=ed[i].v,w=ed[i].w;

            if(dst[u]+w<dst[v]) dst[v]=dst[u]+w,Q.push(v);

        }

    }

}

int main()

{

    n=read(),m=read(),s=read();

    cnt=n;

    bldTr1(rt1,1,n); bldTr2(rt2,1,n);

    while(m--)

    {

        int opt=read(),u,v,w;

        if(opt==1)

        {

            u=read(),v=read(),w=read();

            edAdd(u,v,w); continue;

        }

        u=read(); optL=read(),optR=read(); w=read();

        add(opt==2?rt1:rt2,1,n,u,w,opt);

    }

    SPFA(s);

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

    puts("");

    return 0;

}

巴特西

Codeforces787D - Legacy

Description

Solution

Code

最新文章

热门文章