分析

• 因为求解最大距离，所以使用最短路径，设$x_i$为第i头奶牛所在的位置。根据题目中的条件，有下列不等式：

（1）$x_i \le x_{i+1}, 1 \le i < n$；

（2）$x_b - x_a \le L \iff x_b \le x_a + L$；

（3）$x_b - x_a \ge D \iff x_a \le x_b - D$；

• 以上条件就是题目中能够得到的所有条件，只有相对关系，因此如果存在答案的话，这些位置也可以在坐标轴上平移的。

• 我们发现这里没有一个点可以到达所有点，我们也无法确定从哪个点出发可以遍历所有边，因此可以设置一个虚拟源点，$x_0=$0号点，对应的值为0（即dist[0]=0）。

• 可以令$x_i \le x_0$，这样的话可以从0号点到达其他任意点，可以遍历所有的边。真实代码实现的时候，不需要将0号点建立出来，可以在spfa开始的时候将所有点入队。

• 如何判断不存在满足要求的方案？判断是否存在负环。

• 对于如何判断如果 1 号奶牛和 N 号奶牛间的距离可以任意大，我们可以固定$x_1=0$，判断最终$dist[N]$是不是无穷大，是无穷大的话相当于1号点和N号点没有限制关系。相当于求一下1号点到N号点的最短路径。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 21010, INF = 0x3f3f3f3f;

int n, m1, m2;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int q[N], cnt[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool spfa(int size) {

    int hh = 0, tt = 0;
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);

    for (int i = 1; i <= size; i++) {
        q[tt++] = i;
        dist[i] = 0;
        st[i] = true;
    }

    while (hh != tt) {

        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    q[tt++] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

int main() {

    scanf("%d%d%d", &n, &m1, &m2);
    memset(h, -1, sizeof h);

    for (int i = 1; i < n; i++) add(i + 1, i, 0);
    while (m1--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (a > b) swap(a, b);
        add(a, b, c);
    }
    while (m2--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (a > b) swap(a, b);
        add(b, a, -c);
    }

    if (spfa(n)) puts("-1");
    else {
        spfa(1);
        if (dist[n] == INF) puts("-2");
        else printf("%d\n", dist[n]);
    }

    return 0;
}