做了几题最短路题吧，随便写点什么。
是真的会被卡，当成平方算法用叭。
强推胜者树实现。
把 1 点连到多点，那就再新建 1 个中间点，把中间点与多点连边，再把那 1 点与中间点连边即可。
这个中间点就象征了这个点集，与该点连边，就是 1 点到多点。
把 1 点 与 1 行/列 连边，行/列 即为点集
把 1 点 与 区间 连边，用类似线段树的方法表示点集
最短路当然不是裸的最短路，总是有 1 些奇怪的限制，比如第 2 短路，什么最短路不能等于什么东西，向左不能走多少次，云云。
但其实问题的关键，就是设计表示当前决策的状态，及转移的方式。
这里就是思维的关键！
先需要状态拆分，再利用性质，1 些很妙的关键点，找到这题的解法。
毕克讲的，最短路长度大于点数就有负环，不过这是基于 SPFA 实现的，所以判负环的时间复杂度，就是 SPFA 的复杂度，平方级的。
判断不等式方程组是否有解，其实是把约束条件：xi-xj>S 转化为 xi>xj+S,xi-xj<S 转化为 xj>xi-S，最后判 1 下负环，就可以知道有没有解了。
在处理最小割的问题时，会因为图的特殊性，而造成答案的特殊性，当所有割边方案能用 1 条连续曲线串起来的话，那此图就是对偶图。
平面图就是对偶图。
因为 1 条连续的线等同于 1 种割的情况，这其实就像 1 条路径，跑最短路就是最小割了。
讲的粗略，可自行看其他资料。
对偶图的最小割问题可以转化为最短路问题。
狼抓兔子，NOIp 2017提高组初赛问题求解第 2 题。
对于每 1 条边 u->v:w 若 dis[u]+w==dis[v]，则 u->v 连 1 条有向边，这样就得到了 dijkstra 图啦。
令此为有向无环图(DAG)，所以边权不存在负数。
可以最短路计数啦。
你会最短路吗？
你会 LCA 吗？
那好，支配树就……
支配树，就是由关键点构成的树，何谓关键点？
从出发点 s 到 u 的所有最短路径中，都会经过的点，就是关键点。
关键点会在 1 条路径上吗，会有分叉吗？悬念在此，埋下，先姑且当是对的叭。
设离 u 最的近的关键点是 p，那么 p 向 u 连边，这样就是 1 颗支配树了。
可以从 u 追溯的它的父亲，父亲的父亲即点到根的路径，就可以得到 s->v 所有的关键点了。
现在原图跑 1 遍 dijkstra，构建 dijkstra 图，按拓扑序有序的 1 个 1 个的解决问题。
现在我们求离 u 最近的关键点，考虑它的入度的点，即所有的 v->u 中的 v。
而 v 已是我们求解过的东西了。也就是说，我们已经知道了 v 的关键点路径，是不是取个交集就是 u 的关键点路径了？
何谓交集，也就是 LCA 的 LCA 罢了。
这也解决了 1 个悬念，关键点都在 1 条路径上。应该不是伪证吧？
不写东西就忘了啊。
对于 NOIp 非常爱考的最短路。
我们要想清楚几点，问题与最短路有关否？可否转化为最短路问题？是否借助最短路的某些性质？状态和转移如何？
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：最短路的 1 点延伸”