题面：https://www.luogu.com.cn/problem/P9370
显然只有从 \(0\) 出发不经过 \(H\) 能到达的点是有用的。
首先，考虑跑多源最短路，将 \(arr=0\) 的点都作为源点（当然 \(0\) 也是源点）。不难发现这样转化后，这些点即可视作 \(arr=1\)。
对于 \(arr=2\) 的点，由于能使用除以二技能的次数很少，不妨考虑建分层图。
具体地，原图为第 \(0\) 层图，总共建 \(K+1\) 层图。第 \(l\) 层的点 \(u\) 表示到达 \(u\) 点前恰好使用 \(l\) 次技能的状态。
但是注意到使用技能时的转移相当于松弛一条负权边，这破坏了使用 \(dijkstra\) 算法的条件。
我们进行如下修改:
对于不同层的点，我们先取出层数小的点。
对于相同层的点，我们先取出 \(dis\) 小的点。
这样相当于先让一层的点全部扩展完再进入下一层，而由于高层图不会干扰到低层图，所以当前层的最短路肯定是对的。
而进入下一层时，有些点的 \(dis\) 不等于 \(+\infty\)，这相当于这些点先被一个虚点扩展了一轮，不影响正确性。
具体的算法流程就不必多提了。
特别地，当使用了特别多次技能时，最终的 \(dis\) 会很小。
注意到题目比较答案的规则，粗略估计当 \(dis<10^-7\) 时，再使用技能就没有意义了。即 \(10^5*10^9*\frac{1}{2^K}>=10^-7\)，得\(K<=69\)。
综上，我们通过建分层图并修改 \(dijkstra\) 取出点的顺序解决了此题，复杂度 $(O(NK+MK)*log(NK+MK))。