HDU-3592 World Exhibition

差分约束。

很容易看出两种约束方式，然后建图。而且题目要求排序不能乱，于是加上第三种约束。

求最长就跑一遍最短路啊就行了。

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <deque>

#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<<30

using 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 <int> 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
");
		else if (d[n]==MAX) printf("-2
");
		else printf("%d
", d[n]-d[1]);
	}
	return 0;
}