\(Description\)

有\(n\)个点。你有\(Q\)种项目可以选择（边都是有向边，每次给定\(t,u,v/lr,w\)）：

t==1，建一条\(u\to v\)的边，花费\(w\)；

t==2，由\(u\)向\([l,r]\)中任意一些点连边，每次花费\(w\)；

t==3，由\([l,r]\)中任意一些点向u连边，每次花费\(w\)。

最后求使给定的\(s\)到达点\(i(1\leq i\leq n)\)的最小花费。

\(Solution\)

花费看成每条边的边权，全都连上可以最后直接求最短路。

看到区间操作，能想到线段树。。吗？

原n个点我们还保留。假如连边\((u\to [l,r],w)\)，那么像区间修改一样，\(u\)向代表\([l,r]\)的节点连边权为\(w\)的边。

但只这样连上去了却回不到\(n\)个点上。可以把每个点向其左右儿子连边权为\(0\)的边，表示\([l,r]\)的节点就会真的和\([l,r]\)这些点相连（就直接代表了这些点）。

因为是有向边，对于连边\([l,r]\to u\)我们需要另一棵线段树完成。

线段树节点从\(n+1\)编号，叶节点直接用\(1\sim n\)编号很方便，对操作\(1\)可以直接连边。

要给所有节点标不同的号，就不用struct了。

//249ms 73800KB#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define gc() getchar()//#define MAXIN 200000//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)#define mp std::make_pair#define pr std::pair
         
          typedef long long LL;const int N=100005*9,M=100005*(8+34);//M=8N+2Qlognconst LL INF=0x3f3f3f3f3f3f3f3fll;//longlong!int Enum,H[N],nxt[M],to[M],len[M],tot,son[N][2];LL dis[N];std::priority_queue
          
            q;//char IN[MAXIN],*SS=IN,*TT=IN;#define AddEdge(u,v,w) (to[++Enum]=v,nxt[Enum]=H[u],H[u]=Enum,len[Enum]=w)//()！用到三目运算符 #define lson son[x][0]#define rson son[x][1]void Build2(int &x,int l,int r){ if(l==r) {x=l; return;} x=++tot; Build2(lson,l,l+r>>1), Build2(rson,(l+r>>1)+1,r); AddEdge(x,lson,0), AddEdge(x,rson,0);}void Build3(int &x,int l,int r){ if(l==r) {x=l; return;} x=++tot; Build3(lson,l,l+r>>1), Build3(rson,(l+r>>1)+1,r); AddEdge(lson,x,0), AddEdge(rson,x,0);}void Modify(int l,int r,int x,int L,int R,int t,int u,int w){ if(L<=l && r<=R) { t==2?AddEdge(u,x,w):AddEdge(x,u,w); return; } int m=l+r>>1; if(L<=m) Modify(l,m,lson,L,R,t,u,w);//not rt<<1! if(m
           
            dis[x]+len[i]) dis[v]=dis[x]+len[i], q.push(mp(-dis[v],v)); }}int main(){ int n=read(),Q=read(),S=read(),rt2,rt3; tot=n, Build2(rt2,1,n), Build3(rt3,1,n); for(int t,u,v,l,r,w; Q--; ) { if((t=read())==1) u=read(),v=read(),w=read(),AddEdge(u,v,w); else u=read(),l=read(),r=read(),w=read(),Modify(1,n,t==2?rt2:rt3,l,r,t,u,w); } Dijkstra(S); for(int i=1; i<=n; ++i) printf("%I64d ",dis[i]==INF?-1ll:dis[i]); return 0;}