题意:
一张图上有 n 个点,现在做 m 次操作,操作总共有 3 种:
- 1 a b c: 从 a 到 b 连一条权值为 c 的单向边。(t=1)
- 2 a b c d:从 a 到 [b, c]中的每个点都连一条权值为 d 的单向边。(t=2)
- 3 a b c d:从 [b, c]中的每个点都往 a 连一条权值为 d 的单向边。(t=3)
- 最后给你一个起点 s
分析:
- n比较大,并且有区间建边的操作,抛弃 建边的思想。
- 那就通过数据结构实现区间建边。假设我们从 1 号点往 [2, 9] 中的点连边。我们需要线段树建一棵树,每个点可以到达它的两个子节点。
因为是单向边,所以得建两棵树,然后跑一遍DJ
代码
//暴力连边会炸,考虑区间连边 #include<bits/stdc++.h> #define fir first #define sec second #define ls now<<1 #define rs now<<1|1 #define ll long long using namespace std; const int N=2e6+10; int n,m,s,cnt,tot; int id[2][N],ver[N],nex[N],h[N]; ll dis[N],pri[N]; priority_queue<pair<ll,int > > q; inline void adk(int x,int y,ll z) { nex[tot]=h[x]; ver[tot]=y; pri[tot]=z; h[x]=tot++; } inline void add(int x,int y,int z,int f) { if(f==0) adk(x,y,z); else adk(y,x,z); } inline void build(int now,int l,int r,int f) { if(l==r) { id[f][now]=l; return ; } id[f][now]=++cnt; int mid=(l+r)>>1; build(ls,l,mid,f);build(rs,mid+1,r,f); add(id[f][now],id[f][ls],0,f); add(id[f][now],id[f][rs],0,f);//父连子 } inline void nect(int now,int l,int r,int v,int x,int y,ll z,int f) { if(l>=x&&r<=y) { add(v,id[f][now],z,f); return ; } int mid=(l+r)>>1; if(x<=mid) nect(ls,l,mid,v,x,y,z,f); if(mid<y) nect(rs,mid+1,r,v,x,y,z,f); } int main() { memset(h,-1,sizeof(h)); scanf("%d%d%d",&n,&m,&s); cnt=n; build(1,1,n,0); build(1,1,n,1); int op,x,l,r;ll w; while(m--) { scanf("%d",&op); if(op==1) { scanf("%d%d%lld",&l,&r,&w); nect(1,1,n,l,r,r,w,0); } else { scanf("%d%d%d%lld",&x,&l,&r,&w); nect(1,1,n,x,l,r,w,op-2); } } memset(dis,0x3f,sizeof(dis)); dis[s]=0; q.push(make_pair(0,s)); while(!q.empty()) { int k=q.top().sec;q.pop(); for (int i=h[k];~i;i=nex[i]) { int j=ver[i]; if(dis[j]>dis[k]+pri[i]) { dis[j]=dis[k]+pri[i]; q.push(make_pair(-dis[j],j)); } } } for (int i=1;i<=n;i++) printf("%lld ",(dis[i]>1e16 ? -1:dis[i])); return 0; }