题目链接：Legacy - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题解:
考虑题目中一个点向区间连边，如真的对区间中的每一点分别连边后跑最短路，时间空间都要炸。
因为是一个点向区间连边，考虑线段树。
1到n构造两颗区间线段数
观察上图（从网上搬的）
两颗线段树，一颗入树父亲向儿子连边，用来优化指向叶子的边（左边的树）一颗出树儿子向父亲连边用来优化从叶子指出的点（右边的树）两棵树完全相同。
每个叶子为表示一个星球（可以理解为拆点处理入边和出边），对应的星球之间连一条边，边权为0，因为一个点到自己不花费代价（图中黄色的边）
对于题中给出的操作，操作一可以与操作二等价（也可以与操作三等价）理解为一个点可以去一个区间。
操作二从第二个树上的叶子v向第一颗树上对应的区间连边（与线段树操作相同）
操作三从第一个树上的叶子v向第二颗颗树上对应的区间连边（与上图不太相同，可以自己画图理解）
最后从s点跑最短路
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
const int M=4e6+10;
#define int long long//数据比较大，会爆int
int tot,n,q,s,cnt,root,nxt[M],go[M],hd[M],dx[M],vis[M],dis[M],jz[M],ans,mi,mx;
void add(int x,int y,int w)
{
nxt[++tot]=hd[x],go[tot]=y,jz[tot]=w,hd[x]=tot;
return ;
}
void build(int x,int l,int r,int lx,int lim)//用lim将第一颗树和第二棵树一起处理
{
if(l==r)
{
x=x+lim;
if(x>mx)mx=x;
dx[++cnt]=x;
return ;
}
int mid=(l+r)>>1;
if(lx==1)add(x+lim,x*2+lim,0),add(x+lim,x*2+1+lim,0);
if(lx==2)add(x*2+lim,x+lim,0),add(x*2+1+lim,x+lim,0);
build(x*2,l,mid,lx,lim);
build(x*2+1,mid+1,r,lx,lim);
}
void search(int x,int l,int r,int lt,int rt,int v,int w,int lx)
{
if(lt<=l&&rt>=r)
{
if(lx==1)add(v,x,w);
else add(x+root-1,v,w);
return ;
}
int mid=(l+r)>>1;
if(lt<=mid)search(x*2,l,mid,lt,rt,v,w,lx);
if(rt>mid)search(x*2+1,mid+1,r,lt,rt,v,w,lx);
return ;
}
struct node
{
int id,zhi;
bool operator<(const node& a)const {return zhi>a.zhi;}
node(int x,int y){id=x,zhi=y;}
};
void dij(int x)
{
memset(dis,0x7f,sizeof(dis));
priority_queue<node> q;
dis[x]=0;
q.push(node(x,0));
while(!q.empty())
{
int u=q.top().id;q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=hd[u];i;i=nxt[i])
{
int v=go[i];
if(dis[v]>dis[u]+jz[i])
{
dis[v]=dis[u]+jz[i];
if(!vis[v])q.push(node(v,dis[v]));
}
}
}
return ;
}
signed main()
{
scanf("%lld%lld%lld",&n,&q,&s);
build(1,1,n,1,0);
root=mx+1;//第二颗树的root
build(1,1,n,2,mx);//从第二棵树的点表示为mx+1,mx+2,mx+3而不是mx,2*mx,2*mx+1节约空间不然会MLE。
mx=0,mi=1e9;
for(int i=1;i*2<=cnt;i++)//dx存叶子，考虑线段树过程以及两颗线段树相同，可以得出第i(i<=cnt/2)或i-cnt/2(i>cnt/2)个的对应线段树节点为i,
{
if(dx[i]>mx)mx=dx[i];
if(dx[i]<mi)mi=dx[i];
add(dx[i],dx[i+cnt/2],0);
add(dx[i+cnt/2],dx[i],0);//黄色边，即自己向自己连边
}
for(int i=1;i<=q;i++)
{
int lx,l,r,v,w;;scanf("%lld",&lx);
if(lx==1)
{
scanf("%lld%lld%lld",&v,&l,&w);r=l;
search(1,1,n,l,r,dx[v+cnt/2],w,1);
}
if(lx==2)
{
scanf("%lld%lld%lld%lld",&v,&l,&r,&w);
search(1,1,n,l,r,dx[v+cnt/2],w,1);
}
if(lx==3)
{
scanf("%lld%lld%lld%lld",&v,&l,&r,&w);
search(1,1,n,l,r,dx[v],w,2);
}
}
dij(dx[s]);//最短路
for(int i=1;i<=n;i++)
{
if(dis[dx[i]]==9187201950435737471) dis[dx[i]]=-1;//特殊处理不连通
printf("%lld ",dis[dx[i]]);dis存的是线段树节点
}
return 0;
}
别人的建图
void build(int p,int l,int r){
if(l==r){a[l]=p;return ;}
int mid=(l+r)/2;
add(p,p<<1,0),add(p,p<<1|1,0);
add((p<<1)+K,p+K,0),add((p<<1|1)+K,p+K,0);
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
提前计算第一颗树的最大值，计为K.
对于i存i的对应线段树节点。
其他差别不大
标签：int,lim,线段,add,建图,Legacy,mx,lx,dis From： https://www.cnblogs.com/storms11/p/17988040