前言
这个东西比较简单易懂。
正文
问题引入 ⇒ \Rightarrow ⇒ CF786B （PLUS）
现在有一个 n ( 1 ≤ n ≤ 1 0 5 ) n(1 \leq n \leq 10^5) n(1≤n≤105) 个节点的有向图，现在给出 m ( 1 ≤ m ≤ 1 0 5 ) m(1 \leq m \leq 10^5) m(1≤m≤105) 条信息描述这个图的边，信息有三种：
- 给出三个数 u , v , w u,v,w u,v,w，表示连接一条有向边 ( u , v ) (u,v) (u,v) ，权值为 w w w。
- 给出四个数 u , l , r , w u, l, r, w u,l,r,w，表示从 u u u 向 [ l , r ] [l,r] [l,r] 中所有的点分别连一条有向边，权值都是 w w w。
- 依然给出四个数 u , l , r , w u,l,r,w u,l,r,w，表示 [ l , r ] [l,r] [l,r] 中所有的点分别向 u u u 连一条有向边，权值都是 w w w。
- （原题没有）给出五个数 l 1 , r 1 , l 2 , r 2 , w l_1, r_1, l_2, r_2, w l1,r1,l2,r2,w，表示 [ l 1 , r 1 ] [l_1,r_1] [l1,r1] 中所有的点分别向 [ l 2 , r 2 ] [l_2,r_2] [l2,r2] 中所有的点连一条有向边。
我们需要求出这个图的单源最短路。
基本算法讲解
暴力建图是不可能的。
初始化
将每个点分为入点和出点，一个点 u u u 被分为 u i n u_{in} uin 和 u o u t u_{out} uout (学过网络流的 d a l a o \mathrm{dalao} dalao们应该很清楚这是什么意思)，接着，对于所有入点和出点，分别构建一颗线段树维护，我们称之为入树和出树，出树中区间 [ l , r ] [l,r] [l,r] 对应节点的子树中的叶子节点是原图中 [ l , r ] [l,r] [l,r] 的节点的出点，入树同理。对于入树中的非叶子节点，分别向它的左右儿子连一条权值为 0 0 0 的有向边，而对于出树中的所有非根节点，向它的父亲节点连一条边权为 0 0 0 的边。接着对于所有原图上的点，连接一条出点和入点之间无向边(这是为了防止一些奇怪问题)。
比如 n = 4 n = 4 n=4 的时候，我们构建的线段树和边就是这个样子的：
建图
现在我们需要想办法将原图转化，尽量减少边的数目。
对于出树中某个节点，其表示的区间为 [ l 1 , r 1 ] [l_1,r_1] [l1,r1]，这个节点有一条有向边连接了入树中的另一个节点，其对应区间为 [ l 2 , r 2 ] [l_2, r_2] [l2,r2]， 那么可以视为在原图中，满足 ∀ u ∈ [ l 1 , r 1 ] , v ∈ [ l 2 , r 2 ] , ( u , v ) ∈ E \forall~u\in [l_1, r_1], v\in [l_2, r_2], (u,v) \in E ∀ u∈[l1,r1],v∈[l2,r2],(u,v)∈E。
-
单点 t o \mathrm{to} to 单点：对于一条边 ( u , v ) (u,v) (u,v)，可以直接转化为另一条边 ( u o u t , v i n ) (u_{out}, v_{in}) (uout,vin) 。
-
单点 t o \mathrm{to} to 区间：设单点为 u u u, 区间为 [ l , r ] [l,r] [l,r]。众所周知，一个区间在线段树中会被分成不多于 log 2 ( r − l + 1 ) \log_2 (r-l+1) log2(r−l+1) 个子区间，对于每一个分出的子区间 [ l ′ , r ′ ] [l',r'] [l′,r′] ，都连接一条从 u o u t u_{out} uout 到这个子区间在入树中的对应节点的有向边。
比如 u = 4 , [ l , r ] = [ 1 , 3 ] u=4,[l,r] = [1,3] u=4,[l,r]=[1,3] 的时候，可以这样连边： -
区间 t o \mathrm{to} to 单点：和 单点 t o \mathrm{to} to 区间 类似，不说了。
-
区间 t o \mathrm{to} to 区间：设两个区间为 [ l 1 , r 1 ] , [ l 2 , r 2 ] [l_1, r_1],[l_2, r_2] [l1,r1],[l2,r2]，边的权值为 w w w ，应用上面的方法，我们可以对于两个区间的所有子区间分别两两连边，但是这样的边的数量是 O ( log 2 2 n ) O(\log_2^2 n) O(log22n) 的。正确的姿势是构建一个虚点 p p p，用 区间 t o \mathrm{to} to 单点 的方法，连接 [ l 1 , r 1 ] [l_1, r_1] [l1,r1] 到 p p p，这些边的权值是 w w w，接着用 单点 t o \mathrm{to} to 区间 ，连接 p p p 到 [ l 2 , r 2 ] [l_2, r_2] [l2,r2] ，边权都是 0 0 0。
尾声
接下来只需要在新图上跑一次单源最短路就好啦，此时源点是原图源点的出点。
Code
PS：这是原题的代码，不是加强之后的代码
const int maxn = 1e5 + 5, maxlg2n = 20;
int n;
struct Edge {
int v, nex; LL w;
Edge(int v = 0, LL w = 0, int nex = 0) : v(v), w(w), nex(nex) {}
} E[maxn * maxlg2n << 2];
int hd[maxn << 3], tote;
void addedge(int u, int v, LL w) {
E[++tote] = Edge(v, w, hd[u]), hd[u] = tote;
}
struct STNode {
int ls, rs, l, r;
} nd[maxn << 3];
int inid[maxn], outid[maxn], itr_rt, otr_rt, nd_cnt;
void build_tr(int& o, int l, int r, bool fl) {
o = ++nd_cnt, nd[o].l = l, nd[o].r = r;
if (l == r) {
if (fl) inid[l] = o, addedge(o, outid[l], 0), addedge(outid[l], o, 0);
else outid[l] = o;
return ;
}
int mid = (l + r) >> 1;
build_tr(nd[o].ls, l, mid, fl);
build_tr(nd[o].rs, mid + 1, r, fl);
if (fl) addedge(o, nd[o].ls, 0), addedge(o, nd[o].rs, 0);
else addedge(nd[o].ls, o, 0), addedge(nd[o].rs, o, 0);
}
void addedge_sig_to_sig(int u, int v, LL w) {
addedge(outid[u], inid[v], w);
}
void addedge_seq_to_sig(int p, int l, int r, int u, LL w) {
if (r < nd[p].l || l > nd[p].r) return ;
if (l <= nd[p].l && nd[p].r <= r) {
addedge(p, inid[u], w);
return ;
}
addedge_seq_to_sig(nd[p].ls, l, r, u, w);
addedge_seq_to_sig(nd[p].rs, l, r, u, w);
}
void addedge_sig_to_seq(int p, int u, int l, int r, LL w) {
if (r < nd[p].l || l > nd[p].r) return ;
if (l <= nd[p].l && nd[p].r <= r) {
addedge(outid[u], p, w);
return ;
}
addedge_sig_to_seq(nd[p].ls, u, l, r, w);
addedge_sig_to_seq(nd[p].rs, u, l, r, w);
}
LL dis[maxn << 3]; int vis[maxn << 3];
priority_queue< pair<LL, int> > pq;
void dij(int src) {
for (int i = 1; i <= nd_cnt; i++) dis[i] = -1;
dis[src] = 0, pq.push(make_pair(0, src));
while (!pq.empty()) {
int u = pq.top().second; pq.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = hd[u]; i; i = E[i].nex) {
int v = E[i].v;
if (dis[v] == -1 || dis[v] > dis[u] + E[i].w)
dis[v] = dis[u] + E[i].w,
pq.push(make_pair(-dis[v], v));
}
}
}
int main() {
int q, s;
scanf("%d%d%d", &n, &q, &s);
build_tr(otr_rt, 1, n, false), build_tr(itr_rt, 1, n, true);
for (int i = 1; i <= q; i++) {
int t, u, v1, v2; LL w;
scanf("%d", &t);
if (t == 1) {
scanf("%d%d%lld", &u, &v1, &w);
addedge_sig_to_sig(u, v1, w);
} else if (t == 2) {
scanf("%d%d%d%lld", &u, &v1, &v2, &w);
addedge_sig_to_seq(itr_rt, u, v1, v2, w);
} else {
scanf("%d%d%d%lld", &u, &v1, &v2, &w);
addedge_seq_to_sig(otr_rt, v1, v2, u, w);
}
}
dij(outid[s]);
for (int i = 1; i <= n; i++) printf("%lld ", dis[inid[i]]);
return 0;
}