题解

思路推导

先从 $s$ 和 $t$ 各运行一次 Dijkstra。记城市 $v$ 的两个最短路距离为 $a_v$ 和 $b_v$，把它看成平面上的点 $(a_v,b_v)$，点权为 $p_v$。

Tavas 选择半径，相当于把关于第一维的阈值向右移动，并获得新扫过的所有未使用点；Nafas 的行动则把第二维阈值向上移动。已经满足第一维阈值或第二维阈值的点都已被使用。因此，一个局面只需记录两个当前阈值和轮到谁行动。

将两种距离分别离散化。设第一维有 $X$ 个不同值，第二维有 $Y$ 个不同值。状态 $(i,j)$ 表示第一维前 $i$ 行和第二维前 $j$ 列的并集已经被使用。记 $F_{i,j}$ 为轮到 Tavas 时，从此以后 Tavas 得分减 Nafas 得分的最优值；记 $G_{i,j}$ 为轮到 Nafas 时的对应值。

做法

记 $V(i,j)$ 为前 $i$ 行且位于第 $j$ 列之后的点权和。若 Tavas 把阈值从 $i$ 移到 $x$，本次收益为 $V(x,j)-V(i,j)$，随后进入 $G_{x,j}$。为了满足本次至少获得一座城市，终点行 $x$ 必须在第 $j$ 列之后含有点。无需停在一个没有新点的行：删去这样的末段不会改变本次收益，还会给自己保留更多后续选择。

因此

其中 $x>i$ 且第 $x$ 行在第 $j$ 列之后非空。若不存在这样的行，则已经没有未使用点，状态值为 $0$。

对称地，记 $H(i,j)$ 为前 $j$ 列且位于第 $i$ 行之后的点权和，则

其中 $y>j$ 且第 $y$ 列在第 $i$ 行之后非空。

按 $i$、$j$ 均递减的顺序计算状态。对每个固定的 $j$，维护第一条转移中所有已计算候选的最大值；在同一行从右向左扫描时，维护第二条转移中候选的最小值。这样每个状态只需常数时间。

二维前缀和同时维护点权和与点数。点权和用于计算 $V,H$，点数用于判断一次行动是否确实获得了城市，不能用点权和是否非零代替，因为城市价值允许为零或负数。

正确性证明

任意时刻，Tavas 已选择过的半径形成一个非递减阈值。更小的后续半径不会获得新城市，因而不是合法行动；Nafas 同理。所以所有已使用城市恰为两个距离前缀的并集，状态 $(i,j)$ 完整描述了未来游戏。

在 $F_{i,j}$ 中，枚举 Tavas 下一次阈值的最后一个新非空行，转移收益恰好是本轮所有新获得城市的价值和，且枚举覆盖全部合法行动。随后 $G_{x,j}$ 按最优策略给出剩余游戏的得分差，所以取最大值就是 Tavas 的最优决策。$G$ 的最小值转移同理描述 Nafas 的最优决策。终止状态没有未使用城市，未来得分差为零。按状态包含的未使用城市数归纳，两组转移得到所有状态的真实最优值。

维护的后缀最大值和最小值分别恰好包含公式要求的所有合法终点，因此优化不改变转移集合。最终 $F_{0,0}$ 的符号即为所求结果。

部分分算法

当 $n\le18$ 时，可以用二进制集合记录已使用城市，枚举双方所有不同距离前缀并进行极大极小搜索。

当 $n\le300$ 时，可以保留二维阈值状态，并在每个状态中直接枚举下一条行或列，复杂度为三次方。

复杂度分析

两次最短路的时间复杂度为 $O((n+m)\log n)$。离散化后的动态规划有 $O(n^2)$ 个状态，每个状态为常数转移，时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。