莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 求最大值即求最短路（负环）
2. 奶牛排在队伍中的顺序和它们的编号是相同的：x[i] <= x[i+1] + 0
3. 一些奶牛相互间存有好感：b <= a + L
4. 一些奶牛相互间非常反感：a <= b - D;
5. 第一问：如果存在负环则一定不满足要求，把所有点都入队做一遍 spfa
6. 第二问：把 1 号点入队，如果 dist[n] == INF,则距离可以任意大，即两者互不约束
7. 第三问：把 1 号点入队，做一遍 spfa，输出 dist[n]

#include<bits/stdc++.h>

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],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++;
}

int spfa(int num)
{
    //因为可能会做两遍 spfa，所以要初始化
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    queue<int> q;
    for(int i=1;i<=num;i++)
    {
        q.push(i);
        st[i]=true;
    }

    while(q.size())
    {
        auto t=q.front();
        q.pop();
        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 0;

                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }

    // 1 号奶牛和 N 号奶牛间的距离可以任意大
    if(dist[n]==INF) return -2;

    // 1 号奶牛和 N 号奶牛间可能的最大距离
    return dist[n];
}

int main()
{
    cin>>n>>m1>>m2;

    memset(h,-1,sizeof h);

    // x[i] <= x[i+1] + 0
    for(int i=1;i<n;i++) add(i+1,i,0); 

    // b <= a + c
    while(m1--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c); 
    }

    // a <= b - c;
    while(m2--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(b,a,-c); 
    }

    if(!spfa(n)) cout<<-1<<endl;
    else cout<<spfa(1)<<endl;

    return 0;
}