题意

分别给出\(ml\)和\(md\)对，关于n头奶牛位置的关系，求1号到n号奶牛的最大距离是多少

每一对ml的关系转化成不等式就是： \(A - B \le C\)

相应的，每一对md的关系转化成不等式就是：\(A - B \geq C\) (\(A\)，\(B\)是两头奶牛的位置，\(C\)是他们相差的距离)

思路

看到多元的不等式组，我们就可以考虑使用差分约束来求解此题

ml移项过后成了: \(A \le B + C\)

相当于是：\(B\)向\(A\)做了一条长度为\(C\)的边

md移项过后成了: \(B \le A - C\)

相当于是：\(A\)向\(B\)做了一条长度为\(-C\)的边

做法

因为此题有负边权，所以我们要用spfa来判环

-从一个源点开始求最短路，这条源点连向所有的边，保证图联通。如果有环的话，说明没有合法方案，直接输出\(-1\)

-接下来再从点1(也就是初始点)开始求最短路，如果最终的答案等于初始的极大值，说明他们之间的距离无穷远，直接输出\(-2\)

-最后，如果没有上面的问题，直接输出\(1\) - \(n\)的距离即可

\(Code\)

#include<bits/stdc++.h> 
using namespace std;

struct edge{
	int u, v, d, nex;
}g[1010100];
//存图

int n, ma, mb, a, b, c, dis[1010100] = {0}, first[1010100] = {0}, cnt = 0, vis[1010100] = {0}, du[1010100] = {0};

void update(int u, int v, int d){
	g[++cnt] = (edge){u, v, d, first[u]}, first[u] = cnt;
}
//建图

int spfa(int f){
	for(int i = 0; i <= n; i++) du[i] = 0, vis[i] = 0;
	memset(dis, 0x3f, sizeof(dis));//初始值赋极大值
	queue<int>p;
	p.push(f), vis[f] = 1, dis[f] = 0;
	while(!p.empty()){
		int nex = p.front();
		p.pop(), vis[nex] = 0;
		for(int i = first[nex]; i; i = g[i].nex){
			if(dis[nex] + g[i].d < dis[g[i].v]){
				dis[g[i].v] = dis[nex] + g[i].d;
				if(!vis[g[i].v]){
					vis[g[i].v] = 1, p.push(g[i].v), du[g[i].v]++;
					if(du[g[i].v] > n) return -1;//判断是否存在负权环
				}
			}
		}
	}
	return dis[n] == 0x3f3f3f3f ? -2 : dis[n];//如果没有更新这个点，输出-2
}

int main(){
	scanf("%d %d %d", &n, &ma, &mb);
	while(ma--){
		scanf("%d %d %d", &a, &b, &c);
		update(a, b, c);
	}
	while(mb--){
		scanf("%d %d %d", &a, &b, &c);
		update(b, a, -c);
	}
    //根据前面推出来的式子建图
	for(int i = 1; i <= n; i++) update(0, i, 0);//源点连接每一个点，防止图不联通
	if(spfa(0) == -1) printf("-1");//如果有负权环，输出-1
	else printf("%d", spfa(1));
	return 0;
}