差分约束系统是一种特殊的不等式组，它包含N个变量x1......xn，以及M组限制条件，每组限制条件都是由两个变量作差
小于一个常数组成的，形如X1-X2<=Ck(其中Ck为常数）。这类问题我们可以建一个有向图用最短路来解决。
对于X1-X2<=Ck我们只需要从点1向点2连一条有向边，边权为Ck，从任一点开始跑最短路，如果不存在负环，那么单源
最短路的解即为原题的一组解。
试想为什么会这样？
果要求xi − xj ≤ a，则建立一条从pj 到pi 长度为a 的边
以任意一点为起点求单源最短路，则一定有di − dj ≤ a
所以保证了约束条件成立，如果存在负环那最短路是无限短，原题就无解。
原文：https://www.cnblogs.com/Hoyoak/p/11414333.html