对于一系列约束条件进行转化建图，最终转化为最短路的模型。

如给定以下条件：
$$
x_2-x_1\leq c_1
$$

$$
x_3-x_2\leq c_2
$$

$$
…
$$

$$
x_n-x_{n-1}\leq c_{n-1}
$$

求 $max(x_n-x_1)$ 。即 $x_n-x_1\leq c$ ，求 $c$ 的最小值。注意到约束关系 $x_i-x_j\leq c$ 类似于最短路的关系 $dis[v]\leq dis[u]+w(u,v)$ ，对比可以得到：建立边 $add(j,i,c)$ ，然后跑spfa最短路（有负权边），得到的值即为要求的最大值。若有负环，那么无解。

若得到的关系为 $x_i-x_j\geq c$ ，那么可以转化为 $x_j\leq x_i-c$ ，建边 $add(i,j,-c)$ 。

为了判断连通性，可以建立超级源点，从源点向所有点建立 $add(0,i,0)$ ，并且跑一遍spfa(0)。

例：Layout G

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define main mian
using namespace std;
const int N=1005;
const int M=40005;
int n,ml,md,a,b,d;
struct EDGE
{
	int nxt,to,wei,;
}edge[M];
int head[N],tot;
inline void add(int x,int y,int v)
{
	edge[++tot].nxt=head[x];
	edge[tot].to=y;
	edge[tot].wei=v;
	head[x]=tot;
}
queue<int> q;
int vis[N],dis[N],circle[N];
void spfa(int s)
{
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(circle,0,sizeof(circle));
	q.push(s);
	vis[s]=1,dis[s]=0;
	while(!q.empty())
	{
		int now=q.front(); q.pop(); vis[now]=0;
		for(int i=head[now];i;i=edge[i].nxt)
		{
			int tt=edge[i].to;
			if(dis[now]+edge[i].wei<dis[tt])
			{
				dis[tt]=dis[now]+edge[i].wei;
				circle[tt]=circle[now]+1;
				if(circle[tt]>=n)
				{
					puts("-1");exit(0);
				}
				if(!vis[tt])
				{
					vis[tt]=1;
					q.push(tt);
				}
			}
		}
	}
	
}
int main()
{
	int n;
	scanf("%d%d%d",&n,&ml,&md);
	for(int i=1;i<=n;i++) add(0,i,0);
	for(int i=1;i<=ml;i++)
	{
		scanf("%d%d%d",a,b,d);
		add(a,b,d);
	}
	for(int i=1;i<=md;i++)
	{
		scanf("%d%d%d",a,b,d);
		add(b,a,-d);
	}
	spfa(0);
	spfa(1);
	if(dis[n]==INF) puts("-2");
	else printf("%d",dis[n]);
	return 0;
}