『题解』ABC261Ex Game on Graph
题目链接
震惊！这个题竟然被神犇 szs 归进了博弈论里！我真的没看出来除了题面还有哪里像博弈论（也许是因为我菜）。
转移方式很显然，按照题面说的做就行了。那么正解也就呼之欲出了。
但是我知道大家都会正解，就是魔改的堆优化 Dijkstra，参考上一篇题解即可。所以我想说的是一种歪解，以及它是歪解的原因。
这个歪解是记搜。那么为什么记搜就是歪解呢？魔改的堆优化 Dijkstra 又是干什么的呢？
我的歪解提交记录。在比赛的时候用这个歪解可以 AC，但是新加了 hack 数据以后就不行了。
我们回头看一下 Takahashi 和 Aoki 的转移，前者是尽可能最小，后者是尽可能最大，前者尽可能不走环，后者尽可能走环。我们举一些例子可以发现 Takahashi 的转移会受到出边的顺序的影响，而 Aoki 不会。
在 dfs 的时候，因为我们要对环进行处理，所以我们不能边递归边赋值。但是这会导致我们接下来递归到某一个节点，这个节点的后继节点本来是最优策略，但是因为它先被递归到了，没办法继续往下走了。所以枚举出边的顺序不同会导致每局所有可能选择的策略不同，也就是我们上一段所说的 Takahashi 的转移会受到出边的顺序的影响，而 Aoki 不会。
这里奉上一个相关的样例，如果有不懂的可以用这个来手模一下：
Input:
6 10 3
2 4 5
2 3 2
3 2 3
4 3 8
1 2 4
2 6 7
2 1 1
1 6 3
3 1 6
5 3 6
Output:
17
那么魔改的堆优化 Dijkstra 就是来保证枚举点的顺序正确的。正确性就不证明了。