RT，这道题的标签包含差分约束，说明存在图论做法。

图论做法是什么呢？SPFA。但是 SPFA 被卡到最劣是和 Bellman-Ford 的复杂度一样的，因此数据强度应该允许 Bellman-Ford 通过，但显然本题数据范围太大，不使用极其高超的卡常技巧是无法通过的。

以上摘自 OI-Wiki。

或者请求撤下“差分约束”的标签。毕竟，应该有数据可以把 SPFA 卡到爆炸。