思路就是简单地用最短路跑差分约束，但最短路算法用的不是 spfa，而是另一个 Bellman–Ford 算法的变种，叫 Goldberg–Radzik 算法，算法细节可以看 这篇论文。简述一下就是考虑满足 $d(u)+w(u,v) \le d(v)$ 的边诱导的子图，子图中的环只有零环和负环，找到负环直接结束，零环缩点，然后按剩下的 DAG 的拓扑序松弛节点。上面说的是标准做法，这个做法实际上就是本题的正解，但实际实现一般用的是简化方法：直接忽略一些零环中的边。从最短路的角度来说，简化后最多是多跑几轮，对于本题来说则有点像是乱搞。算法的实际速度很快，不仅通过了 本题，连 Hack spfa 也轻松过掉了，跑 最短路 的效果也还可以。