差分约束系统，就是给定一些 $ x_i - x_j >= d $ 的不等式，求出其中的一组解。我们可以转化为最短路来解决该类问题。

<h1>实现</h1>

PS:以下讨论整数情况，浮点数请注意精度。
我们对于每一组 $ x_i - x_j >= d $ 的不等式，从$ j $ 向 $ i $ 连一条长度为d的边。
可能有人会问：如果是其他状态的不等式呢？
我们可以利用以下转换：
1、 $ x_i - x_j >= dist $ 可以转换为 $ x_j - x_i &lt;= -dist $
2、 $ x_i - x_j &lt; dist $ 可以转换为 $ x_i - x_j &lt;= dist - 1 $
3、 $ x_i - x_j == dist$ 可以转换为 $ x_i - x_j &lt;= dist and x_j - x_i &lt;= dist $

跑完后每个结点的dist及为结果。
一般在计算$ x_1 - x_n $最大解时跑最短路，最小解时跑最长路。
如果图中有负环，则无解。

<h1>例题</h1>

CodeVS4416
给出n个形如 $ x_i - x_j &lt;= d $ 或 $ x_i - x_j >= d $ 的不等式，求一组$ x_1 - x_n $最大的解。
如果无解输出-1，差无限大输出-2。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <climits>

const int MAXN = 1000 + 5;

int N,M,K;

struct Node{
    int dist;
    int count;
    bool inQueue;
    struct Edge{
        Node s,t;
        int w;
        Edge *next;

        Edge(Node s,Node t,int w) : s(s), t(t), w(w), next(s->firstEdge) {}
    };
    Edge *firstEdge;
}node[MAXN];

inline void add(int u,int v,int w){
    node[u].firstEdge = new Node::Edge(&node[u],&node[v],w);
}

inline bool spfa(){
    for(int i = 1;i <= N;i++){
        node[i].dist = INT_MAX;
        node[i].inQueue = false;
    }
    std::queue<Node *> q;
    node[1].dist = 0;
    node[1].inQueue = true;
    q.push(&node[1]);
    while(!q.empty()){
        Node *v = q.front();q.pop();
        v->inQueue = false;
        for(Node::Edge *e = v->firstEdge;e;e = e->next){
            if(e->t->dist > v->dist + e->w){
                e->t->dist = v->dist + e->w;
                if(!e->t->inQueue){
                    q.push(e->t);
                    e->t->inQueue = true;
                    e->t->count++;
                    if(e->t->count > N) return false;
                }
            }
        }
    }
    return true;
}

int main(){
    scanf("%d%d%d",&N,&M,&K);
    for(int u,v,w,i = 1;i <= M;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    for(int u,v,w,i = 1;i <= K;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(v,u,-w);
    }
    if(!spfa())
        printf("%d",-1);
    else{
        if(node[N].dist == INT_MAX)
            printf("%d",-2);
        else
            printf("%d",node[N].dist);
    }
    return 0;
}