奇怪的最短路问题
原题：HDU6166/P5304/LOJ#3087
法一
维护最短路和次短路以及它们的来源点。具体有待补充。
法二
一种套路：多源多汇最短路。
多源多汇怎么做？
建一个超级源点和超级汇点，但是这样从源点出来就可以0权到汇点。
解决方案：
随机划分：
$p=\frac{1}{4}$，T次成功概率：$1-(1-p)^T$，虽然 $20$ 次随机成功概率为 $99.68\%$，但毕竟是概率，不够靠谱并且基于RP。
二进制分组：
按照二进制的一个位置上的 $01$ 值来划分谁是源点谁是汇点，由数据范围知最多 $17$ 次划分，每次需要跑两遍。有点卡时限但能过。
指针分析
复习指针？
题目中给的关系实际上是一些边的关系，但是这些边有些限制。
某些边有激活条件，例如一个指针得先指向某个地址之后才能访问。
小模拟，将题目操作转化为代码。
Bellman-ford 思想：不断松弛，在过程中实现 $4$ 种操作并同时维护。
实现思路1：
set维护每个点能到哪些点实现思路2：状态压缩
关于优化：
基于RP：减少松弛轮数
基于卡常：快读
基于随机化：
shuffle+clock()卡时间
老算法焕发新生。
果国的奇妙旅行
带决策的期望。
#define 卡 票
定义 $E(u)$ 表示 $u$ 到终点的期望。
此题目要求在最优策略下到终点的期望抽卡次数，可以发现所谓最优策略就是贪心：如果我抽到的卡走过去的期望 $E(v)$ 较 $E(u)$ 而言减小了，即 $E(u) > E(v)$，那么我们就可以走到 $v$，定义这就是一次成功的决策。
也就是说，如果我抽到的卡能使我的期望减小，那么就走，否则扔掉重来。于是我们的转移就可以分为两种情况：一种是 $v$ 向 $u$ 转移；另一种是不转移。
我们又发现，从结果来看，如果 $u$ 走到 $v$ 这个决策是成功的，那么 $v$ 走到 $u$ 的决策一定是不成功的，因为 $E(u) > E(v)$，就一定 $E(u) > E(v)$ （满篇废话，然而这种显著的废话往往是最难发现并利用的）。
综上，我们就认为 $u$ 的转移是有方向的。
根据以上的情况讨论，不难得到 $E(u)$ 转移如下：
$$E(u)=\sum_{v\in e(u)}^{E(v) < E(u)}{\frac{E(v)}{deg(u)}}+\sum_{v\in e(u)}^{E(v)\geq E(u)}{\frac{E(u)}{deg(u)}}+1$$
设 $x=\sum[v\in e(u) \And E(v) \geq E(u)],d=deg(u)$
化简过程：
$$E(u)=\frac{1}{d}(\sum_{v\in e(u)}^{E(v) < E(u)}{E(v)}+xE(u))+1$$
$$dE(u)=\sum_{v\in e(u)}^{E(v) < E(u)}{E(v)}+xE(u)+d$$
$$(d-x)E(u)=\sum_{v\in e(u)}^{E(v) < E(u)}{E(v)}+d$$
得到：
$$E(u)=\sum_{v\in e(u)}^{E(v) < E(u)}{\frac{E(v)}{d-x}}+\frac{d}{d-x}$$
十分抽象的一点是：我确定边的方向需要 $u$ 和 $v$ 的期望来进行大小比较，然而期望又需要边的方向来更新。问题就是如何打破这个循环。
数学上的推导不太可能了，考虑从更新顺序入手。
目前这里的方法是填表法，考虑使用刷表法，即对于每个 $u$ 去更新它的 $v$。考虑使用Dijkstra算法。而且不难发现，$E(u)$ 的值随着更新不断减小（分母变大）。
像这种破逻辑的环很难解决，切入口不好找，因此这里直接放结论。
一开始设置 $E(u)=+\infty$ ，然后让 $E(v)$ 从小到大更新 $E(u)$ 。
（为什么这样可行我也不会证。可能需要数学归纳法。）
最后，因为 $E(u)$ 的定义是 $u$ 到终点的期望，因此搜索时应该从终点开始搜。（思考：从起点搜结果会受影响吗？）
推完了。
至于怎么实现还得是Dijkstra。
事实上，指针分析 和 果国的奇妙旅行 都不是最短路的题目，但是借用了最短路算法的思想，不愧为《最新颖的一集》。