差分约束。
很容易看出两种约束方式，然后建图。而且题目要求排序不能乱，于是加上第三种约束。
求最长就跑一遍最短路啊就行了。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define N 1234#define M 56789#define ll long long#define MAX 1<<30using namespace std;int read(){ int x=0, f=1; char ch=getchar(); while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return f*x;}struct edge{int y, n, v;} e[M]; int fir[N], en;int n, x, y, c[N], d[N], ans, o;bool b[N];void Add(int x, int y, int v){ en++, e[en].y=y, e[en].v=v, e[en].n=fir[x], fir[x]=en;}int main(){ int t=read(); while (t--) { en=ans=0; rep(i, 1, n) fir[i]=0; scanf("%d%d%d", &n, &x, &y); rep(i, 1, x) { int a=read(), b=read(), c=read(); Add(a, b, c); } rep(i, 1, y) { int a=read(), b=read(), c=read(); Add(b, a, -c); } rep(i, 2, n) Add(i, i-1, 0); deque q; rep(i, 1, n) b[i]=1, c[i]=1, d[i]=MAX, q.push_back(i); d[1]=0; while (!q.empty()) { x=q.front(); o=fir[x]; y=e[o].y; q.pop_front(); b[x]=0; if (c[x] > n) { ans=-1; break; } while (o) { if (d[y]>d[x]+e[o].v) { d[y]=d[x]+e[o].v; if (!b[y]) b[y]=1, c[y]++, !q.empty()&&d[y]<=d[q.front()] ? q.push_front(y) : q.push_back(y); } o=e[o].n, y=e[o].y; } } if (ans==-1) printf("-1\n"); else if (d[n]==MAX) printf("-2\n"); else printf("%d\n", d[n]-d[1]); } return 0;}