题意:
给有向带权图,然后在其中加边,有三种操作:
- u->v加一条权值为w的边。
- [l,r]->v加(r-l+1)条权值为w的边。
- u->[l,r]加(r-l+1)条权值为w的边。
然后询问以s点为起点到其他所有点的最短路。
题解:
线段树优化建图。
考虑建两棵线段树A,B,然后:
- A线段树的每个非叶子节点的儿子向该节点连权值为0的边。
- B线段树的每个非叶子节点向该节点的儿子连权值为0的边。
- B线段树的每个叶子节点向A线段树对应的叶子节点连权值为0的边。
这其中A线段树的叶子节点就代表原图中的节点,其余节点都是用来优化建图的。
对于加边的操作:
- 建立虚点p1,p2。
- A线段树上的区间[l,r]向p1连权值为0的边。
- p1向p2连权值为w的边。
- p2向B线段树上的区间[l,r]连权值为0的边。
最后跑dijkstra即可,注意dijkstra中向堆中加点的操作有变化。
PS.数组尽量往大的开QAQ。
参考代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=0x7f7f7f7f7f7f7f7f;
const int MAXN=1e5+9;
const int MAXM=1e5+9;
int n,m,s;
int rta,rtb,tot;
int ls[MAXN<<5],rs[MAXN<<5];
int V[MAXN<<5];
struct Edge
{
int v,nxt;
ll w;
} edge[MAXN<<5];
int cnt=0,fir[MAXN<<5];
void addedge(int u,int v,ll w)
{
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].nxt=fir[u];
fir[u]=cnt++;
}
void build(int l,int r,int &rt,bool flag)
{
rt=++tot;
if(l==r)
{
if(flag)
V[l]=rt;
return;
}
int mid=(l+r)>>1;
build(l,mid,ls[rt],flag);
build(mid+1,r,rs[rt],flag);
if(flag)
{
addedge(ls[rt],rt,0);
addedge(rs[rt],rt,0);
}
else
{
addedge(rt,ls[rt],0);
addedge(rt,rs[rt],0);
}
}
void deal(int l,int r,int leafA,int leafB)
{
if(l==r)
{
addedge(leafB,leafA,0);
return;
}
int mid=(l+r)>>1;
deal(l,mid,ls[leafA],ls[leafB]);
deal(mid+1,r,rs[leafA],rs[leafB]);
}
void update(int L,int R,int p,int l,int r,int rt,bool flag)
{
if(L<=l&&r<=R)
{
if(flag)
addedge(rt,p,0);
else
addedge(p,rt,0);
return;
}
int mid=(l+r)>>1;
if(L<=mid)
update(L,R,p,l,mid,ls[rt],flag);
if(R>mid)
update(L,R,p,mid+1,r,rs[rt],flag);
}
void link(int a,int b,int c,int d,ll w)
{
update(a,b,++tot,1,n,rta,1);
addedge(tot,tot+1,w);
update(c,d,++tot,1,n,rtb,0);
}
ll dis[MAXN<<5];
bool used[MAXN<<5];
void dijkstra(int st)
{
priority_queue<pair<ll, int> > q;
while(!q.empty())
q.pop();
memset(dis,INF,sizeof(dis));
dis[st]=0;
q.push(make_pair(0,st));
while(!q.empty())
{
int u=q.top().second;
q.pop();
if(used[u])
continue;
used[u]=1;
for(int i=fir[u];i!=-1;i=edge[i].nxt)
{
int v=edge[i].v;
ll w=edge[i].w;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
q.push(make_pair(-dis[v],v));
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
memset(fir,-1,sizeof(fir));
build(1,n,rta,1);
build(1,n,rtb,0);
deal(1,n,rta,rtb);
for(int i=1; i<=m; i++)
{
int op,u,w,l,r;
scanf("%d",&op);
if(op==1)
{
scanf("%d%d%d",&u,&l,&w);
link(u,u,l,l,w);
}
else if(op==2)
{
scanf("%d%d%d%d",&u,&l,&r,&w);
link(u,u,l,r,w);
}
else
{
scanf("%d%d%d%d",&u,&l,&r,&w);
link(l,r,u,u,w);
}
}
dijkstra(V[s]);
for(int i=1; i<=n; i++)
if(dis[V[i]]!=INF)
printf("%lld ",dis[V[i]]);
else
printf("-1 ");
return 0;
}