CF786B Legacy
题意：
给定\(n\)个点
一共有\(m\)个连边，边有三种。
1.从\(u_i\)到\(v_i\)的一条长度为\(w_i\)的边。
2.从\(u_i\)到\([l,r]\)的一条长度为\(w_i\)的边。
3.从\([l,r]\)到\(v_i\)的一条长度为\(w_i\)的边。
问从\(s\)到每一个点的最短路。
\(n,m<=10^5\)
很有意思的题目
显然不可以暴力连边，我们可以拿线段树的思想，让线段树的一个区间代表一个点。
拿两颗线段树分别维护区间连点和点连区间
以点连区间为例，直接拿点连树1的区间。而树1上面的边可以以费用0走到孩子节点。
对应区间连点，就是那树2的区间直接连点。而树2上面的边可以以费用0走到父亲节点。
连接树1树2就行了
Code:
#include <cstdio>
#include <cstring>
#include <queue>
#define ls ch[now][0]
#define rs ch[now][1]
#define ll long long
using namespace std;
const int N=100010;
const ll inf=0x3f3f3f3f3f3f3f3f;
int head[N<<3],to[N<<4],Next[N<<4],cnt;
int n,m,s,ch[N<<3][2],tot,typ;
ll edge[N<<4];
void add(int u,int v,ll w)
{
edge[++cnt]=w;to[cnt]=v;Next[cnt]=head[u];head[u]=cnt;
}
int build1(int l,int r)
{
if(l==r) return l;
int now=++tot;
int mid=l+r>>1;
ls=build1(l,mid);
rs=build1(mid+1,r);
add(now,ls,0);
add(now,rs,0);
return now;
}
int build2(int id,int l,int r)
{
if(l==r) return l;
int now=++tot;
int mid=l+r>>1;
ls=build2(ch[id][0],l,mid);
rs=build2(ch[id][1],mid+1,r);
add(ls,now,0);
add(rs,now,0);
add(id,now,0);
return now;
}
void connect(int now,int l,int r,int L,int R,int pos,ll w)
{
if(l==L&&r==R)
{
if(typ==1) add(pos,now,w);
else add(now,pos,w);
return;
}
int mid=L+R>>1;
if(r<=mid)
connect(ls,l,r,L,mid,pos,w);
else if(l>mid)
connect(rs,l,r,mid+1,R,pos,w);
else
connect(ls,l,mid,L,mid,pos,w),connect(rs,mid+1,r,mid+1,R,pos,w);
}
int root[2];
void init()
{
scanf("%d%d%d",&n,&m,&s);
tot=n;
root[0]=build1(1,n);
root[1]=build2(root[0],1,n);
int opt,u,v,l,r;ll w;
for(int i=1;i<=m;i++)
{
scanf("%d",&opt);
if(opt==1)
{
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w);
}
else if(opt==2)
{
scanf("%d%d%d%lld",&u,&l,&r,&w);//点连区间
typ=1;
connect(root[0],l,r,1,n,u,w);
}
else
{
scanf("%d%d%d%lld",&v,&l,&r,&w);
typ=0;
connect(root[1],l,r,1,n,v,w);
}
}
}
queue <int> q;
ll dis[N<<3];
int used[N<<3];
void work()
{
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
q.push(s);
while(!q.empty())
{
int u=q.front();
used[u]=0;
q.pop();
for(int i=head[u];i;i=Next[i])
{
int v=to[i];
ll w=edge[i];
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if(!used[v])
{
used[v]=1;
q.push(v);
}
}
}
}
for(int i=1;i<=n;i++)
{
if(dis[i]==inf)
printf("-1 ");
else
printf("%lld ",dis[i]);
}
}
int main()
{
init();
work();
return 0;
}
2018.7.20