最短路

今日继续垫底系列 T1题意理解错误暴力写挂 T2怒敲 $n \le 4$ 求根公式然后发现答案还得排序。。 $\text{score：0 + 10 + 0 = 10 rk：27/27}$ Problem A：游戏题目描述ysgh是一名Herthstone大师。现在他遇到了一个很严峻的问题： 场上总共有 $n+m$ 个随从，其中ysgh控制着 $n$ 个，对手控制着 $m$ 个。每个随从有自己的血量。 如果ysgh在这一回合成功解掉了对手的所有随从，则ysgh获胜。否则下一回合对手直接骑脸，ysgh就会输掉。 ysgh现在手里仅有一场牌，属性如下： 进行 $d$ 次，每一次等概率随机一个在场上的未死亡随从（包括自己和对手的）并且对其造成一点伤害。若不存在未死亡随从，则不进行此次攻击。一个随从未死亡当且仅当其血量严格大于 $0$。每一次攻击后，所有血量小于等于 $0$ 的随从立即死亡。 ysgh想要知道，他有多大概率可以取胜，也就是多大的概率使得在使用这张牌后，对手的随从全部死亡。 特别提醒：由于描述与实际游戏规则有出入，一切以实际题面描述为准。 数据范围对于所有测试数据，满足 $1 ...

题意即为带修（临时）最短路 先随便提一条最短路出来，那么修改可分为四种情况： 该边在最短路上，且数值变小 该边在最短路上，且数值变大 该边在最短路外，且数值变小 该边在最短路外，且数值变大 那么对于情况 $1, 3, 4$，显然是十分容易处理的，那么问题就在情况 $2$ 设最短路经过点 $e_1, e_2, e_3, …$ 考虑到新的最短路必定与原最短路有相同的一段前缀与后缀（可以为空），设 $dis2_{i, j} (i < j)$ 表示不经过路径 $e_ie_j$ 的最短路，所以答案即为 $\min \{dis2 (e_ie_j) (i < j)\}$ 那么便两遍 $Dijstra$ 分别求出 $1, n$ 到每个点 $p$ 的最短路 $pre_p, suf_p$，并且对于最短路上的点 $e_i$，求出其在最短路上的前驱边 $from_{e_i}$ 与后继边 $nxt_{e_i}$，对于每个不在最短路上的点 $p$，求出点 $1$ 至 $p$ 中最后一个在原最短路上的点的后继边 $from_p$ 及点 $p$ 至 $n$ 中第一个在原最短路上的点的后继边 $nxt_ ...