震惊！这个题竟然被神犇 szs 放进了博弈论里！我真的没看出来除了题面还有哪里像博弈论（也许是因为我菜）。
转移方式很显然，按照题面说的做就行了。那么正解也就呼之欲出了。
但是我知道大家都会正解，就是魔改的堆优化 Dijkstra，所以我想说的是一种歪解，以及它是歪解的原因。
歪解就是记搜。歪解除了没有正解的堆优化，再不少什么了。那么为什么没有堆优化就变成歪解了呢？堆优化又是干什么的呢？
我的歪解提交记录。在比赛的时候用这个歪解可以 AC，但是新加了 hack 数据以后就不行了。
我们回头看一下 \(たかはし\) 和 \(あおき\) 的转移，前者是尽可能最小，后者是尽可能最大，前者尽可能不走环，后者尽可能走环。那么也就是说 \(たかはし\) 的转移会受到出边的顺序的影响，而 \(あおき\) 不会。举个例子，如果一个点指向了很多个点，这些点所导致的结果有的会导致环，是 INFINITY，有的不能导致环，是 NOT INFINITY，但是这些点的枚举顺序我们不知道。根据前面所述可知，这样的例子会导致 \(たかはし\) 做出错误的决策。那么优先队列就是让枚举的点有序，因为 \(たかはし\) 要让结果尽可能最小，所以就用小根堆维护即可。
显然 dfs 不可以用堆优化，除非你改变了存边的顺序从而保证了枚举顺序的正确性，否则它永远都只是歪解。当然，改变存边顺序以后，时间复杂度显然不会优于正解（应该是差不多，但是常数就不知道了），所以还不如用正解。