题目大意
原题的题目大意已经很明确了要这个干嘛
给定一些孤立点，将要进行两种操作：
-
若两点之间不可以通过 \(1\) 类边连通，则在两点之间连双向 \(1\) 类边
-
若 \(u_1,v_1\) 和 \(u_2,v_2\) 均可以通过 \(1\) 类边连通，则从 \(u_1\to v_1\) 的唯一路径上的所有点均向 \(u_2\to v_2\) 的唯一路径上的所有点连单向非 \(1\) 类边。
在完成所有操作后求出从给定的 \(s\) 出发的单源最短路。
前置知识
如果你不熟悉以下内容，那还是换一篇题解看吧。
-
树链剖分
-
线段树优化建图
思路分析
首先显然有一个 \(O(n\log^3n)\) 的大力树剖做法，但这个做法过于暴力，时间和空间都不允许，无法通过本题。
考虑优化这个做法，我们发现，对于每一个重链都在线段树上进行一次连边实在太过于暴力，时间复杂度高就来源于这里。
我们知道，一条重链是一颗树上独立的部分，我们可以为每一条重链预处理出一条路径，使得从这个点可以直接到达重链上的所有点。这样在树剖的时候对于每一个重链只需要连一条边就可以了。
那剩下的部分怎么办呢？不用怕，直接怼一个线段树优化建图上去就可以了，反正只有一个区间，对时间复杂度没有影响。
这样我们就得到了一个时间复杂度为 \(O(m\log^2n)\)，空间复杂度为 \(O(n\log n)\) 的不那么暴力的做法，足以通过本题。
详细解释
上面的部分解释了一下大致思路，但还有亿些细节。
- 如何预处理出重链路径？
对于每一个点，建立两个新的点，入点和出点，然后由这个点的入点向该点连边，该点向出点连边。
同时，自己的出点向自己的重儿子的出点连边，自己的重儿子的入点向自己的入点连边。这样就形成了两条路径，一条往下的出路径和一条往上的入路径。
- 如何使用线段树优化建图？
跟正常的线段树优化建图差不多，只需要在树剖的配合下上树就行了。
struct STn{int l,r;};//没什么用的结构体
struct ST{
STn a[P<<2];//开四倍
void build(int p,int l,int r){
a[p].l=l;a[p].r=r;
if(a[p].l==a[p].r){
idt[p][0]=idt[p][1]=rnk[l];//rnk[l]才是对应的点，idt[p][0]是入出的节点编号，idt[p][1]是出树的
return ;
}
int mid=(a[p].l+a[p].r)>>1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
idt[p][0]=build_new_point();//动态开点，节约空间
idt[p][1]=build_new_point();
add(idt[p][0],idt[p<<1][0],0,0);//入树和出树连边
add(idt[p][0],idt[p<<1|1][0],0,0);
add(idt[p<<1][1],idt[p][1],0,0);
add(idt[p<<1|1][1],idt[p][1],0,0);
}
void connect(int p,int point,int l,int r,int f){
if(l<=a[p].l&&a[p].r<=r){
if(f) add(point,idt[p][0],0,0);//f=1 表示点向区间连边
else add(idt[p][1],point,0,0);//f=0 表示区间向点连边
return ;
}
int mid=(a[p].l+a[p].r)>>1;
if(l<=mid) connect(p<<1,point,l,r,f);
if(r>mid) connect(p<<1|1,point,l,r,f);
}
}tree;
其他
然后就应该没什么大问题了，但是细节还是很多的。
-
使用并查集维护 \(1\) 类边的连通。
-
入点和出点，入树和出树不要搞混。
-
dfs 时只走树边。
-
这题卡空间，建议使用邻接表存图。
代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N=2500000,P=50100;//n log n 空间
#define inf 0x3f3f3f3f
struct Edge{int v,w;};
vector <Edge> E[N];//邻接表存所有边
int to[P<<1],head[P],nxt[P<<1];//链星存树边
int dfn[P],rnk[P],dep[P],siz[P],son[P],fa[P],top[P];
int idx=1,n,m,in1,in2,in3,in4,in5,op,s;
int query_num,dfs_cnt,id;
int dis[N],vis[N],idt[P<<2][2];
int fat[P];
int find(int x){return fat[x]==x?x:fat[x]=find(fat[x]);}//并查集
int build_new_point(){//动态开点
id++;return id;
}
void add(int u,int v,int c,int f){
if(f==1){idx++;to[idx]=v;nxt[idx]=head[u];head[u]=idx;}//f=1 表示这条边是树边
E[u].push_back(Edge{v,c});
}
struct Query{
int u1,v1,u2,v2,w;
}query[N];
struct Node{
int x,dis;
}now;
bool operator < (Node a,Node b){
return a.dis>b.dis;//大根堆
}
priority_queue <Node> q;
void Dijskra(){//最短路
memset(dis,0x3f,sizeof dis);
q.push(Node{s,0});dis[s]=0;
while(!q.empty()){
now=q.top();q.pop();
if(vis[now.x]) continue;
vis[now.x]=1;
for(auto it:E[now.x]){
int v=it.v;
if(dis[v]<dis[now.x]+it.w) continue;
dis[v]=dis[now.x]+it.w;
q.push(Node{v,dis[v]});
}
}
}
void dfs_1(int s,int gr){//树剖预处理
fa[s]=gr;dep[s]=dep[gr]+1;
siz[s]=1;son[s]=-1;
for(int i=head[s];i;i=nxt[i]){
int v=to[i];
if(v==gr) continue;
dfs_1(v,s);
siz[s]+=siz[v];
if(son[s]==-1||siz[son[s]]<siz[v]) son[s]=v;
}
}
void dfs_2(int s,int tp){
top[s]=tp;
dfn[s]=++dfs_cnt;
rnk[dfs_cnt]=s;
if(son[s]==-1) return ;
add(son[s]+n,s+n,0,0);//入点往上
add(s+2*n,son[s]+2*n,0,0);//出点往下
dfs_2(son[s],tp);
for(int i=head[s];i;i=nxt[i]){
int v=to[i];
if(v==son[s]||v==fa[s]) continue;
dfs_2(v,v);
}
}
struct STn{int l,r;};//没什么用的结构体
struct ST{
STn a[P<<2];//开四倍
void build(int p,int l,int r){
a[p].l=l;a[p].r=r;
if(a[p].l==a[p].r){
idt[p][0]=idt[p][1]=rnk[l];//rnk[l]才是对应的点，idt[p][0]是入出的节点编号，idt[p][1]是出树的
return ;
}
int mid=(a[p].l+a[p].r)>>1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
idt[p][0]=build_new_point();//动态开点，节约空间
idt[p][1]=build_new_point();
add(idt[p][0],idt[p<<1][0],0,0);//入树和出树连边
add(idt[p][0],idt[p<<1|1][0],0,0);
add(idt[p<<1][1],idt[p][1],0,0);
add(idt[p<<1|1][1],idt[p][1],0,0);
}
void connect(int p,int point,int l,int r,int f){
if(l<=a[p].l&&a[p].r<=r){
if(f) add(point,idt[p][0],0,0);//f=1 表示点向区间连边
else add(idt[p][1],point,0,0);//f=0 表示区间向点连边
return ;
}
int mid=(a[p].l+a[p].r)>>1;
if(l<=mid) connect(p<<1,point,l,r,f);
if(r>mid) connect(p<<1|1,point,l,r,f);
}
}tree;
void add_edge_one_to_two(int point,int x,int y,int f){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
if(f) add(point,x+n,0,0);
else add(x+2*n,point,0,0);//注意是 x 不是 top[x]
x=fa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
tree.connect(1,point,dfn[y],dfn[x],f);//剩下的部分用线段树
}
void add_edge_two_to_two(int query_id){
int u1=query[query_id].u1,v1=query[query_id].v1;
int u2=query[query_id].u2,v2=query[query_id].v2;
int w=query[query_id].w;//把询问提取出来
int uu=build_new_point(),vv=build_new_point();
add(uu,vv,w,0);//建两个新的点并在这两点之间连有权值的边
add_edge_one_to_two(vv,u2,v2,1);//出点向路径连边
add_edge_one_to_two(uu,u1,v1,0);//路径向入点连边
}
int main(){
scanf("%d%d%d",&n,&m,&s);
id=3*n;//动态开点的编号从 3n 开始，n+1 到 2n 是入点，2n+1 到 3n 是出点
for(int i=1;i<=n;i++) fat[i]=i;//不要忘了初始化
for(int i=1;i<=m;i++){
scanf("%d",&op);
if(op==1){
scanf("%d%d%d%d%d",&in1,&in2,&in3,&in4,&in5);
if(find(in1)!=find(in2)||find(in3)!=find(in4)) continue;
query[++query_num]=Query{in1,in2,in3,in4,in5};//保存一下询问
}
if(op==2){
scanf("%d%d%d",&in1,&in2,&in3);
if(find(in1)==find(in2)) continue;
add(in1,in2,in3,1);add(in2,in1,in3,1);
fat[find(in1)]=find(in2);
}
}
for(int i=1;i<=n;i++)
add(i+n,i,0,0),add(i,i+2*n,0,0);//先把出入点之间的边连上
for(int i=1;i<=n;i++)
if(!dfn[i]){
dfs_1(i,0);
dfs_2(i,i);
}
tree.build(1,1,n);//不要忘了建树
for(int i=1;i<=query_num;i++)//连一下询问的边
add_edge_two_to_two(i);
Dijskra();
for(int i=1;i<=n;i++)
if(dis[i]==inf) cout<<"-1 ";
else cout<<dis[i]<<' ';
cout<<'\n';
return 0;
}