題解 ： https://xiaoxiaoh.blog.csdn.net/article/details/104188049

一、内容

像其他人一样，奶牛在排队饲料时喜欢靠近他们的朋友。 FJ有N（2 <= N <= 1,000）个编号为1..N的奶牛从左到右按照编号从小到大站在一条直线上等待饲料。牛的数量与它们的编号相同，因为它们可能相当具有挑战性，所以有可能两头或多头奶牛可以在同一位置排队（也就是说，如果我们将每只奶牛看作是位于在数字线上的某个坐标上，那么两个或更多的母牛可以共享相同的坐标）。

一些奶牛喜欢彼此，并希望彼此在一定距离内排队。有些人真的不喜欢对方，并希望至少隔开一定的距离。 ML（1 <= ML <= 10,000）约束的列表描述了哪些母牛彼此相似以及它们可以被分开的最大距离; MD约束的后续列表（1 <= MD <= 10,000）告诉哪些母牛不喜欢彼此以及它们必须被分开的最小距离。

如果可能，您的工作是计算母牛1和母牛N之间满足距离约束的最大可能距离。

Input

第1行：三个空格分隔的整数：N，ML和MD。

第2行.ML + 1：每行包含三个空格分隔的正整数：A，B和D，其中1 <= A <B <= N.奶牛A和B必须至多D（1 <= D <= 1,000,000）。

ML + 2..ML + MD + 1行：每行包含三个空格分隔的正整数：A，B和D，其中1 <= A <B <= N.奶牛A和B必须至少为D 1 <= D <= 1,000,000）。

Output

第1行：一个整数。如果不能排队，则输出-1。如果母牛1和N可以任意分开，输出-2。否则输出母牛1和N之间的最大可能距离。

Sample Input

4 2 1
1 3 10
2 4 20
2 3 3

Sample Output

27

二、思路

• 差分约束

• 差分约束条件：

  • b <= a + L 奶牛 A 和奶牛 B 至多相隔 L 的距离。
  • a <= b - D 奶牛 A 和奶牛 B 至少相隔 D 的距离。
  • s~i~ <= s~i+1~ 后一头奶牛的距离大于前一头
  • 建立超级源点0， x~i~ <= x~0~ 这样从0出发就能遍历所有的边

• 首先从0出发判断有无负环，若有负环输出 -1

• 若无负环则求1 和 n 的最大距离差。 若最大距离差是无穷，输出-2。
  • 最大距离差： x~n~ - x~1~ <= c1 + c2 + .... + cn 后面的一坨就是1到n的最短距离。

三、代码

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1005, M = 2e4 + 5, INF = 0x3f3f3f3f;
struct E {
    int v, next, w;
} e[M];
int n, m1, m2, a, b, w, len = 1, h[N], d[N], cnt[N];
bool vis[N];
void add(int u, int v, int w) {
    e[len].v = v;
    e[len].w = w;
    e[len].next = h[u];
    h[u] = len++;
}
bool spfa(int s) {
    memset(d, 0x3f, sizeof(d));
    memset(cnt, 0, sizeof(cnt));
    memset(vis, false, sizeof(vis));
    d[s] = 0; 
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int j = h[u]; j; j = e[j].next) {
            int v = e[j].v;
            int w = d[u] + e[j].w;
            if (w < d[v]) {
                d[v] = w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] > n) return true;
                if (!vis[v]) vis[v] = true, q.push(v);
            }
        }
    }
    return false; 
}
int main() {
    scanf("%d%d%d", &n, &m1, &m2);
    for (int i = 1; i <= m1; i++) {
        scanf("%d%d%d", &a, &b, &w);
        add(a, b, w); 
    }
    for (int i = 1; i <= m2; i++) {
        scanf("%d%d%d", &a, &b, &w);
        add(b, a, -w); 
    }
    //后一头牛的距离大于前一头 
    for (int i = 1; i <= n; i++) {
        add(i + 1, i, 0);
    }
    //添加超级源点 假定所有点都小于0 
    for (int i = 1; i <= n; i++) {
        add(0, i, 0); 
    } 
    if (spfa(0)) printf("-1");
    else {
        //代表没有负环 那么求下 1 <= n + c  求出最大的c 即从1出发到n的最短距离 
        spfa(1);
        if (d[n] == INF) printf("-2");
        else printf("%d", d[n]);
    }
    return 0;
}