TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1510
  • 题目
  • P1510安置奶牛
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    像每个人一样,奶牛排队吃饭时都喜欢站的和朋友们近一点。FJ有N头站成一条直线等待吃饭的牛(2<=N<=1000)。奶牛们都按照编号的顺序排队,因为他们可能很能挤,可能多头牛站在同一个地方(就是说,如果我们认为牛是安置在一条直线的坐标里,可能多头牛在同一个坐标里)。
    有一些牛喜欢其他牛,所以希望能和其他牛在一定的距离之内。有一些非常不喜欢某些牛,并且希望和它至少保持一定的距离。一个表ML (1 <= ML <= 10,000)包含互相喜欢的牛以及它们之间的最大距离。一个表MD(1 <= MD <= 10,000)描述了不喜欢对方的牛以及他们之间的最小距离。
    你的任务是计算,如果可能,满足要求的1和N的最大距离。

    输入格式

    第一行:三个整数N,ML,MD;
    2~ML+1行:每行包含三个数A,B,D,1 <= A < B <= N,A和B最多分隔D距离。
    ML+2~ML+MD+1:每行包含三个数A,B,D,1 <= A < B <= N,A和B最少分割D距离

    输出格式

    一行,如果不存在这样的队列,输出-1 。 如果牛1可以和N随便分隔多远,输出-2 。其他的情况输出牛1和牛N之间的最大距离。

    样例输入

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

    样例输出

    27


    来源  usaco dec05 gold 翻译by ylmf