第一个求最大值的题目,约束的形式应该是$x_i<=x_j$,表示一条从j到i权重为0的边,小于所有路径中和最小的,因此用最短路。根据三角不等式来思考边的方向,如果$x_i$小于$x_j+c$,那么一定会被j更新,本题的不等关系,$x_i$表示第i头牛的位置。
$$x_{i+1}>=x_i$$ $$x_b-x_a<=c$$ $$x_b-x_a>=c$$
后面的牛的位置一定不在前面的牛的前面,两头牛的距离分别小于等于c大于等于c。本题n号点是超级源点,根据公式1可以走到所有的边。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1010,M=20010,INF=0x3f3f3f3f;
int h[N],e[M],ne[M],w[M],idx;
int cnt[N],dist[N],n,q[N];
bool st[N];
void add(int a,int b,int c){
w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool spfa(int k){
memset(dist,0x3f,sizeof dist);
memset(cnt,0,sizeof cnt);
memset(st,0,sizeof st);
int tt=1,hh=0;
for(int i=1;i<=k;i++){
dist[k]=0;
st[k]=true;
q[0]=k;
}
while(tt!=hh){
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]){
st[j]=true;
q[tt++]=j;
if(tt==N) tt=0;
}
}
}
}
return false;
}
int main(){
memset(h,-1,sizeof h);
int m1,m2;
cin>>n>>m1>>m2;
for(int i=1;i<n;i++) {
//xi<=xi+1 i+1->i 0
add(i+1,i,0);
}
while(m1--){
int a,b,c;
//xb-xa<=c xb<=xa+c b>a
scanf("%d%d%d",&a,&b,&c);
if(a>b) swap(a,b);
add(a,b,c);
}
while(m2--){
int a,b,c;
//xb-xa>=c xa<=xb-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 cout<<dist[n]<<endl;
}
return 0;
}