TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3488
  • 题目
  • P3488【2015多校联训5】疫情延迟
    限制 : 时间限制 : 10000 MS   空间限制 : 165536 KB
    问题描述

    由于A 学校生物实验室里那个不负责的数据分析员,实验室的病毒威力被错误估算,导致了可怕的病毒泄漏,现在病毒即将在校园内传播开来。
    校园里一共有n 个建筑物,生物实验室总是位于一号建筑物且在0 时刻受到病毒入侵。这n 个建筑物由m 条单向道路相连(也有可能有建筑物被孤立)。每条道路有两个信息:它的长度,它是多少年前修建的。当一个建筑物被病毒入侵,从被入侵的时刻起,病毒会从所有由这个建筑物通向其他建筑物的道路按着这条道路的方向以1 个单位每秒的速度行进。
    校长得知这个事情后,决定放弃这个学校逃跑。校长总是位于编号为n 的行政楼,从零时刻开始需要共T 秒来逃出行政楼,且逃出行政楼即视为逃出了这个学校。也就是说,如果病毒入侵行政楼的时间不小于T,则校长能够成功逃离。
    有些时候,校长没有足够的时间逃离,因为病毒到达行政楼的时间太快了。
    为了让校长能够逃离学校,不得不拆除校园内的一些道路以延缓行政楼的被入侵时间(拆除道路视为在0 时刻被拆的道路全部消失)。当然,如果使得病毒根本无法到达行政楼,也是可以的。
    但是,拆除道路会影响学校的历史气息,且破坏程度定义为拆除的道路中最古老的一条的年龄。请求出保证校长能够安全撤离的情况下,最小的破坏程度。

    输入格式

    第一行包含三个整数:n, m, T。
    接下来m 行,每行描述一条有向道路。每行4 个整数,si, ti, Li, Yi,分别表
    示这条道路的起点,终点,长度,这条道路的年龄。

    输出格式

    如果不需要拆除任何道路,输出一行两个数:-1 和行政楼的被感染时刻(当然
    这个时刻大于等于T),以空格隔开。
    否则输出一行包含一个数:最小的破坏程度。

    样例输入

    【样例输入1】
    5 5 15
    1 2 6 35
    2 4 8 40
    1 3 6 45
    3 4 3 25
    4 5 5 50

    【样例输入2】
    3 2 10
    1 2 5 30
    2 3 6 50

    样例输出

    【样例输出1】
    25

    【样例输出2】
    -1 11

    提示

    【样例解释1】

    每条边上的黑字对应这条路的长度,红字对应年龄。校长将在第15 秒逃出学校,
    如果不拆除任何道路,行政楼将在第14 秒受到入侵。你可以拆除4 到5 的道路,
    使得行政楼免于入侵,这样的破坏程度是50。但是最好的方法是拆掉3 到4 之
    间的道路,这样使得行政楼在第19 秒受到入侵,校长就可以逃离了。
    【数据范围】
    对于20%的数据,n, m<=10
    对于60%的数据,n, m<=100.
    对于100%的数据,n<=20000, m<=100000.
    数据保证在不拆除任何道路的情况下,从1 号楼到n 号楼一定存在路径。


    来源  by BZ