题解

思路

把不等式 $x_c-x_{c'}\le y$ 改写为 $x_c\le x_{c'}+y$，并从 $c'$ 向 $c$ 连一条权值为 $y$ 的有向边。只要图中没有负环，一组最短路距离就是一组可行解；存在负环时无解。

子任务 1

小图可以枚举所有不重复顶点的路径与环。若发现权值和为负的简单环，则无解；否则，每个点的最小简单路径长度构成一组可行解。

子任务 2

增加一个到所有点边权为零的超级源点，使用 Floyd–Warshall 求任意两点最短路。若某个对角线距离为负则存在负环；否则超级源点到各点的距离是一组可行解。

做法

不必显式建立超级源点。把所有点的初始距离设为零并全部放入队列，相当于超级源点向每个点连零边。不断用边做松弛；某个点第 $n+1$ 次进入队列时，说明存在可达负环，输出 NO。若队列清空，则当前距离满足每条边对应的不等式，直接输出。

复杂度

队列优化 Bellman–Ford 的最坏时间复杂度为 $O(nm)$，空间复杂度为 $O(n+m)$。

正确性说明

每条边 $c'\to c$ 的松弛条件正是 $d_c\le d_{c'}+y$。算法结束时所有边都不能继续松弛，因此所有不等式同时成立。若某点被沿松弛路径更新超过 $n$ 次，则该路径必含负环；反之，有负环时对应约束可以无限降低，算法必能检测到。因此输出 NO 当且仅当系统无解。