3366: 「一本通 3.4 练习 2」布局 Layout

内存限制:512 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

**原题来自:USACO 2005 Dec. Gold** FJ 有 $N$ 头奶牛 $(2\le N\le 1000)$,编号为 $1\ldots N$。奶牛们将按照编号顺序排成一列队伍(可能有多头奶牛在同一位置上)。换句话说,假设 $i$ 号奶牛位于 $P_{\!\;i}$,则 $P_{\,1}\le P_{\,2}\le \ldots\le P_{\!\;N}$。 有些奶牛是好基友,它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌,它们希望彼此之间的距离大于等于某个数。 给出 $M_L$ 对好基友的编号,以及它们希望彼此之间的距离小于等于多少;又给出 $M_D$ 对情敌的编号,以及它们希望彼此之间的距离大于等于多少 $(1\le M_L,$ $M_D\le 10^4)$。 请计算:如果满足上述所有条件,$1$ 号奶牛和 $N$ 号奶牛之间的距离($P_{\!\;N}-P_{\,1}$)最大为多少。

输入

第一行:三个整数 $N, M_L, M_D$,用空格分隔。 第 $2\dots M_L+1$ 行:每行三个整数 $A, B, D$,用空格分隔,表示 $P_B-P_A\le D$。 第 $M_L+2\dots M_L+M_D+1$ 行:每行三个整数 $A, B, D$,用空格分隔,表示 $P_B-P_A\ge D$。 保证 $1\le A

输出

一行,一个整数。如果没有合法方案,输出 $\texttt{-1}$. 如果有合法方案,但 $1$ 号奶牛可以与 $N$ 号奶牛相距无穷远,输出 $\texttt{-2}$. 否则,输出 $1$ 号奶牛与 $N$ 号奶牛间的最大距离。

样例输入 复制

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

样例输出 复制

27

提示


数据范围:对于全部数据,$2\le N\le 1000,1\le M_L,M_D\le 10^4,1\le L,D\le 10^6$。

来源/分类