图论 plus
P5304 「GXOI/GZOI2019」旅行者
如果是无向边，那么以所有感兴趣的城市为起点跑一遍 Dijkstra 即可，遇到访问过的点就说明找到了最短路。
但题目已经写清楚可能存在自环和重边，而起点和终点相同不算两两之间，所以还需要额外记录一下起点。
变成有向边后，我们不能在任意一个点处合并最短路了，这就导致最短路会经过从终点出发的一些路径。所以需要额外记录到达每个点起点与最短路不同的次短路。
P3573 「POI2014」RAJ-Rally
我们可以根据经过某个点的路径状况来判断删除哪个点最优。正向和反向分别跑一遍最长路，统计不同长度路径的数量然后合并，删除路径数量从长到短字典序最大的那个点。
但这东西仔细想想不好优化而且还要写高精度，所以还是得想办法得到删除每个点后的最长路。
https://www.luogu.com.cn/blog/xcxcli/P3573
P4745 「CERC2017」Gambling Guide
一般的期望题考虑倒推就行。
设 \(f_u\) 表示从点 \(u\) 走到终点的期望步数，那么有
\[f_u=\frac{\sum_{(u,v)}\min(f_u,f_v)}{deg_u}+1
\]
把 \(\min\) 拆开，设
\[cnt_u=\sum_{(u,v)}[f_v<f_u]\qquad sum_u=\sum_{(u,v),f_v<f_u}f_v
\]
式子化为
\[f_u=\frac{sum_u+(deg_u-cnt_u)\times f_u}{deg_u}+1
\]
整理可得
\[f_u=\frac{sum_u+deg_u}{cnt_u}
\]
发现期望步数大于当前点的点不会对当前点的期望步数造成影响，所以倒着 Dijkstra 一遍即可。因为当前期望步数不是最小的某个点实际期望步数如果是最小，那么将没有点能更新它，产生矛盾。