Super Root 超级源点、加点、加边
特征
- 需要添加边，但是暴力加边时间or空间复杂度不可取；
- 加边是针对某一类点加边；
- 答案最终会汇集到一个点上，一些网络流的题需要建立超级源点和超级汇点。
注意点
- 加边时考虑边权设计；
- 如果要对超级源点加双向边，要考虑周全一些不合法的情况，例如会不会无边权超级传送；
- 加点要算好空间，算好下标。
例题
给定一棵树，$1$ 为根节点，对于树上每条边 $(u, v)$ 都具有一个权值 $w$ 。但是，如果两个节点的高度差为 $k$ ，则可以通过 $p$ 的权值直接到达，求在这棵树上从 $s$ 到 $t$ 的最短路径长度。
多组测试数据。
$1 \le T \le 5$
$2 \le n \le 10^6$
$1 \le u_i,v_i,s,t \le n, u_i \neq v_i, s \neq t$
$1 \le w_i,k \le 10^6$
$0 \le p \le 10^6$
我们发现这道题需要加边跑最短路，然而，$\text{Dijkstra}$ 带上加边会跑到 $O((n+m+n^3)\log (m+n^3)+n^3)$ ，这里极限数据的情况是整棵树有 $\sqrt n$ 层，每层有 $\sqrt n$ 个点，且 $k = 1$ 。即使我们不真正连边，仍然还有 $O((n+m+n^3)\log (m+n^3))$ 的时间复杂度。死得透透的。
因此我们考虑对每一层建立一个超级源点，边权为 $0$ ，再对上下 $k$ 层的超级源点连边，因为这个点既可以上又可以下，所以要连双向边。然鹅，这个方案有一个巨大的问题。
如果我们连双向边，那么最短路会借助超级源点在同一层实现 $0$ 权值跳转，很明显，这是不合法的。于是我们考虑每层加两个超级源点，一个用于向外走，一个向内走，问题就解决了，时间复杂度 $O((5n+m)\log (2n+m))$ 。
给出一个图，每次只能连续走两条边，其权值为两条边权值的和的平方，求以 $1$ 为源点时分别到 $1\sim n$ 的最短路。
$2 \leqslant n \leqslant 10^5,1 \leqslant m\leqslant min(\frac{n(n-1)}{2},2*10^5)$
$1\leqslant v_i,u_i \leqslant n,1 \leqslant w_i \leqslant50,u_i\neq v_i$
同时处理两条边是有些困难的。考虑往图里增加信息。我们发现边权十分小，只有 $50$ 。于是我们想到建分层图，入边 $(u,v,w)$ 即建一条边从第 $w$ 层图 $v$ 点到原图 $v$ 点，出边 $(u,v,w)$ 就是建一条边从原图 $v$ 点到第 $w$ 层图 $v$ 点。这样做正确性显然。
2. 最短路计数
这里要提两个概念
附录
SPFA玄学优化
据某位不知名人士所言，SPFA的时间复杂度可以用 $O(m+n\log n)$ 来拟合，而Dijkstra的时间复杂度为 $O(m\log n)$ 。这意味着如果题目不卡SPFA，则SPFA跑得比Dijkstra还要快。如果卡SPFA，还可以通过SLF、mcfx等优化方法来使SPFA更快。甚至专门卡SPFA的标准版单源最短路径的次优解（$\text{80ms}$）就是使用了SLF-swap优化过的。