原题链接

大概思路

我们已知一组不等式的解可以通过建边然后求最短路/最长路来得出
而这里要求 \(D_n-D_1\) 的最大值，所以我们要求最短路。

补充

为什么要求最短路？
对于任何一组不等式，我们都可以写成 \(a_i-b_i \leq c_i\) 建边含义
假设 \(D_n-D_1\) 有最大值，那么通过这组不等式的组合，一定能得出若干个形似 \(D_n-D_1 \leq k_j\) 的式子，此时便可以得出 \(\max(D_n-D_1)\) 就等于 \(\min(k_j)\)

细节

1. \(D_i\geq D_{i-1}\ (i>1)\ \to D_{i-1}-D_i\leq 0\)
   2.要判断每条边（即每个约束）是否都满足，所以要建立超级源点，判断是否存在负环，不能以点1来判断是否存在负环，因为图不保证联通

code

#include<bits/stdc++.h>
using namespace std;
const int inf=2e9;

int dis[1010];

struct node
{
    int to,len;
};
vector<node> G[1010];
int n;
bool run(int start)
{
    int vis[1010]={0};
    bool in_q[1010]={0};
    fill(dis,dis+1004,inf);
    queue<int>  q;
    q.push(start);
    in_q[start]=1;
    dis[start]=0;

    while(q.size())
    {
        int now=q.front();
        q.pop();
        in_q[now]=0;
        vis[now]++;
        if(vis[now]>=n)
        {
            return 0;
        }
        for(auto next:G[now])
        {
            int to=next.to,len=next.len;
            if(dis[to]>dis[now]+len)
            {
                dis[to]=dis[now]+len;
                if(!in_q[to])
                {
                    q.push(to);
                }
            }
        }
    }
    return 1;
}
int main()
{
    int l,d;
    cin>>n>>l>>d;

    for(int i=1;i<=n;i++) G[0].push_back({i,0});
    for(int i=2;i<=n;i++) G[i].push_back({i-1,0});
    for(int i=1;i<=l;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        G[a].push_back({b,c});
    }

    for(int i=1;i<=d;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        G[b].push_back({a,-c});
    }



    if(!run(0)) puts("-1");
    else
    {
        run(1);
        if(dis[n]==inf) puts("-2");
        else cout<<dis[n]<<endl;
    }

    //for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0;
}