题目描述
原题来自：USACO 2005 Dec. Gold
FJ 有
N
N 头奶牛
(2\le N\le 1000)
(2≤N≤1000)，编号为
1\ldots N
1…N。奶牛们将按照编号顺序排成一列队伍（可能有多头奶牛在同一位置上）。换句话说，假设
i
i 号奶牛位于
P_{\!\;i}
P
i
，则
P_{\,1}\le P_{\,2}\le \ldots\le P_{\!\;N}
P1
≤P2
≤…≤PN
。
有些奶牛是好基友，它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌，它们希望彼此之间的距离大于等于某个数。
给出
M_L
ML
对好基友的编号，以及它们希望彼此之间的距离小于等于多少；又给出
M_D
MD
对情敌的编号，以及它们希望彼此之间的距离大于等于多少
(1\le M_L,
(1≤ML
,
M_D\le 10^4)
MD
≤104)。
请计算：如果满足上述所有条件，
1
1 号奶牛和
N
N 号奶牛之间的距离（
P_{\!\;N}-P_{\,1}
PN
−P1
）最大为多少。
输入
第一行：三个整数
N, M_L, M_D
N,M
L
,M
D
，用空格分隔。
第
2\dots M_L+1
2…ML
+1 行：每行三个整数
A, B, D
A,B,D，用空格分隔，表示
P_A-P_B\le D
PA
−PB
≤D。
第
M_L+2\dots M_L+M_D+1
ML
+2…ML
+MD
+1 行：每行三个整数
A, B, D
A,B,D，用空格分隔，表示
P_A-P_B\ge D
PA
−PB
≥D。
保证
1\le A1≤A1\le D\le 10^6
1≤D≤106.
输出
一行，一个整数。如果没有合法方案，输出
\texttt{-1}
-1. 如果有合法方案，但
1
1 号奶牛可以与
N
N 号奶牛相距无穷远，输出
\texttt{-2}
-2. 否则，输出
1
1 号奶牛与
N
N 号奶牛间的最大距离。
样例输入
4 2 1
1 3 10
2 4 20
2 3 3
样例输出
27
提示
样例说明
这四头牛分别位于
0,7,10,27
0,7,10,27。
数据范围与提示
对于全部数据，
2\le N\le 1000,1\le M_L,M_D\le 10^4,1\le L,D\le 10^6
2≤N≤1000,1≤ML
,MD
≤104,1≤L,D≤106。
来源/分类
ybttg 差分约束系统