1512：排队布局

题目描述

当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。FJ 有 $N$ 头奶牛，编号从 $1$ 到 $N$，沿一条直线站着等候喂食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上。即使说，如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。一些奶牛相互间存有好感，它们希望两者之间的距离不超过一个给定的数 $L$。另一方面，一些奶牛相互间非常反感，它们希望两者间的距离不小于一个给定的数 $D$。

给出 $ML$ 条关于两头奶牛间有好感的描述，再给出 $MD$ 条关于两头奶牛间存有反感的描述。你的工作是：如果不存在满足要求的方案，输出 $-1$；如果 $1$ 号奶牛和 $N$ 号奶牛间的距离可以任意大，输出 $-2$；否则，计算出在满足所有要求的情况下，$1$ 号奶牛和 $N$ 号奶牛间可能的最大距离。

输入格式

第一行三个整数 $N, ML, MD$；

接下来 $ML$ 行，每行三个正整数 $A, B, D$，表示奶牛 $A$ 和奶牛 $B$ 至多相隔 $D$ 的距离（$A < B$）；

接下来 $MD$ 行，每行三个正整数 $A, B, D$，表示奶牛 $A$ 和奶牛 $B$ 至少相隔 $D$ 的距离（$A < B$）。

输出格式

如果不存在满足要求的方案，输出 $-1$；如果 $1$ 号奶牛和 $N$ 号奶牛间的距离可以任意大，输出 $-2$；否则，计算出在满足所有要求的情况下，$1$ 号奶牛和 $N$ 号奶牛间可能的最大距离。

样例

样例输入 #1

4 2 1
1 3 10
2 4 20
2 3 3

样例输出 #1

27

样例解释 #1

• $N=4$ 头奶牛，$ML=2$ 条好感约束，$MD=1$ 条反感约束。
• 好感约束（至多相隔 $D$）：
  1. 奶牛 $1$ 和 $3$ 距离 $\le 10$
  2. 奶牛 $2$ 和 $4$ 距离 $\le 20$
• 反感约束（至少相隔 $D$）：
  1. 奶牛 $2$ 和 $3$ 距离 $\ge 3$
• 奶牛顺序与编号相同，即位置 $x_1 \le x_2 \le x_3 \le x_4$（允许相等）。
• 建立不等式：
  • 顺序约束：$x_{i+1} \ge x_i$（即 $x_i - x_{i+1} \le 0$）
  • 好感约束：$x_3 - x_1 \le 10$，$x_4 - x_2 \le 20$
  • 反感约束：$x_3 - x_2 \ge 3$ 即 $x_2 - x_3 \le -3$
• 求 $x_4 - x_1$ 的最大值（即 $1$ 号和 $N$ 号的距离）。
• 一种可行解：$x_1=0, x_2=7, x_3=10, x_4=27$，满足：
  • $x_3 - x_1 = 10 \le 10$
  • $x_4 - x_2 = 20 \le 20$
  • $x_3 - x_2 = 3 \ge 3$
  • 顺序：$0 \le 7 \le 10 \le 27$
• $x_4 - x_1 = 27$，可以验证无法得到更大的距离（受约束限制），输出 $27$。

数据范围

对于全部数据：

• $2 \le N \le 1000$
• $1 \le ML, MD \le 10^4$
• $1 \le L, D \le 10^6$

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB

注意：本题是差分约束系统求最大值的问题。令 $x_i$ 表示奶牛 $i$ 的位置，则：

1. 顺序约束：$x_{i+1} \ge x_i$，即 $x_i - x_{i+1} \le 0$。
2. 好感约束（$A < B$）：$x_B - x_A \le D$。
3. 反感约束（$A < B$）：$x_B - x_A \ge D$，即 $x_A - x_B \le -D$。 我们需要求 $x_N - x_1$ 的最大值，即满足所有不等式条件下 $x_N - x_1$ 的最大值，等价于以 $1$ 为源点求到 $N$ 的最短路（因为不等式是 $\le$ 形式，求最大值相当于在最短路约束下求最大距离）。使用 Bellman-Ford 或 SPFA 判断负环（无解情况）并计算最短距离。如果 $dis[N]$ 为无穷大（即 $1$ 和 $N$ 之间没有约束限制），则输出 $-2$；如果存在负环则输出 $-1$；否则输出 $dis[N]$。