线段树优化建图的裸题
代码：
#include#include #include #include #include using namespace std;#define rg registervoid read(int &x){ char ch;bool ok; for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1; for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;}const int maxn=2e5+10;int cnt,pre[maxn*20],nxt[maxn*20],h[maxn*10],val[maxn*20],pos[maxn*10];int id,n,m,s;long long dis[maxn*10];bool vis[maxn*10];struct oo{int x;long long y;};priority_queue q;bool operator<(oo a,oo b){return a.y>b.y;}void add(int x,int y,int z){pre[++cnt]=y,nxt[cnt]=h[x],h[x]=cnt,val[cnt]=z;}void build_in(int x,int l,int r){ int mid=(l+r)>>1;id=max(id,x); if(l==r)return pos[l]=x,void(); build_in(x<<1,l,mid),build_in(x<<1|1,mid+1,r); add(x,x<<1,0),add(x,x<<1|1,0);}void build_out(int x,int l,int r){ add(x,x+id,0);int mid=(l+r)>>1; if(x!=1)add(x+id,(x>>1)+id,0);if(l==r)return ; build_out(x<<1,l,mid),build_out(x<<1|1,mid+1,r);}void change_in(int x,int l,int r,int a,int b,int c,int d){ if(a<=l&&b>=r)return add(c,x,d),void(); int mid=(l+r)>>1; if(a<=mid)change_in(x<<1,l,mid,a,b,c,d); if(b>mid)change_in(x<<1|1,mid+1,r,a,b,c,d);}void change_out(int x,int l,int r,int a,int b,int c,int d){ if(a<=l&&b>=r)return add(x+id,c,d),void(); int mid=(l+r)>>1; if(a<=mid)change_out(x<<1,l,mid,a,b,c,d); if(b>mid)change_out(x<<1|1,mid+1,r,a,b,c,d);}void dijkstra(int s){ memset(dis,63,sizeof dis); q.push((oo){s,dis[s]=0}); while(!q.empty()){ int x=q.top().x;q.pop();if(vis[x])continue;vis[x]=1; for(rg int i=h[x];i;i=nxt[i]) if(!vis[pre[i]]&&dis[pre[i]]>dis[x]+val[i]){ dis[pre[i]]=dis[x]+val[i]; q.push((oo){pre[i],dis[pre[i]]}); } }}int main(){ read(n),read(m),read(s);build_in(1,1,n),build_out(1,1,n); for(rg int i=1,t,x,y,u,v;i<=m;i++){ read(t); if(t==1){ read(y),read(x),read(v); add(pos[y]+id,pos[x],v); } if(t==2){ read(u),read(x),read(y),read(v); change_in(1,1,n,x,y,pos[u]+id,v); } if(t==3){ read(u),read(x),read(y),read(v); change_out(1,1,n,x,y,pos[u],v); } } dijkstra(pos[s]); for(rg int i=1;i<=n;i++)printf("%lld ",dis[pos[i]]>1e16?-1:dis[pos[i]]);}