给你一张正边权有向图，Alice 先手，从节点 v 开始，两个人每次沿一条边移动一步，没路走了就游戏结束。

Alice 想最小化经过边的权值和，Bob 想最大化，求最后经过的边的权值和。

\(n\leq 10^5\)

考虑设 \(f_i,g_i\) 分别表示两人先手，从这个节点出发所得到的分数。方程显然。

如果这是个 DAG 的话就做完了。

考虑使用 dij 进行转移

dij 的正确性来自于它每一次取出节点时确保了这个节点已经被完全更新，即权值已经确定。

另一方面，所有满足条件的节点都能够第一时间去更新其他节点。

于是我们每次取出最小的权值进行更新，如果更新的是 \(f_i\) 就直接入队，如果更新的是 \(g_i\) 的话就在它被所有能更新它的节点更新之后入队。

搬运自 Luogu Blog