CodeForces

Luogu

分析

线段树优化连边的板子题？

因为是有向图，建两颗线段树就行了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

struct Edge { int v,w,nxt; } e[N*20];
int head[N<<3];

inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}

int n,m,s;
int tot,root[2];

struct node { int ls,rs; } t[N<<3];

inline void build1(int& o,int l,int r) {
    if (l==r) { o=l; return; }
    o=++tot; int mid=(l+r)>>1;
    build1(t[o].ls,l,mid),build1(t[o].rs,mid+1,r);
    addEdge(o,t[o].ls,0),addEdge(o,t[o].rs,0);
}

inline void build2(int& o,int l,int r) {
    if (l==r) { o=l; return; }
    o=++tot; int mid=(l+r)>>1;
    build2(t[o].ls,l,mid),build2(t[o].rs,mid+1,r);
    addEdge(t[o].ls,o,0),addEdge(t[o].rs,o,0);
}

inline void link1(int o,int l,int r,int ql,int qr,int u,int w) {
    if (ql<=l&&r<=qr) { addEdge(u,o,w); return; }
    int mid=(l+r)>>1;
    if (ql<=mid) link1(t[o].ls,l,mid,ql,qr,u,w);
    if (qr>mid) link1(t[o].rs,mid+1,r,ql,qr,u,w);
}

inline void link2(int o,int l,int r,int ql,int qr,int u,int w) {
    if (ql<=l&&r<=qr) { addEdge(o,u,w); return; }
    int mid=(l+r)>>1;
    if (ql<=mid) link2(t[o].ls,l,mid,ql,qr,u,w);
    if (qr>mid) link2(t[o].rs,mid+1,r,ql,qr,u,w);
}

struct heapnode {
    int u; ll d;
    bool operator <(const heapnode& x) const {
        return d>x.d;
    }
};

ll dis[N<<3];

inline void dijkstra() {
    priority_queue<heapnode> Q; Q.push((heapnode){s,0});
    memset(dis,0x3f,sizeof(dis)); dis[s]=0;
    while (!Q.empty()) {
        heapnode x=Q.top(); Q.pop();
        int u=x.u; ll d=x.d;
        if (d!=dis[u]) continue;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (d+w<dis[v]) dis[v]=d+w,Q.push((heapnode){v,dis[v]});
        }
    }
}

int main() {
    tot=n=read(),m=read(),s=read();
    build1(root[0],1,n),build2(root[1],1,n);
    for (re int i=1;i<=m;++i) {
        int op=read();
        if (op==1) {
            int u=read(),v=read(),w=read();
            addEdge(u,v,w);
        } else {
            int u=read(),l=read(),r=read(),w=read();
            if (op==2) link1(root[0],1,n,l,r,u,w);
            else link2(root[1],1,n,l,r,u,w);
        }
    }
    dijkstra();
    for (re int i=1;i<=n;++i) {
        if (dis[i]>1e18) printf("-1 ");
        else printf("%lld ",dis[i]);
    }
    putchar('\n'); return 0;
}