U19231 打鼹鼠

    • 2通过
    • 37提交
  • 题目提供者 hz2016
  • 评测方式 云端评测
  • 标签
  • 难度 尚无评定
  • 时空限制 3000ms / 256MB

  • 提示:收藏到任务计划后,可在首页查看。
  • 题目背景

    OI商店的仓库里出现了一群恼人的鼹鼠!它们在仓库里到处打洞,还破坏了很多重要的货品!我们面临的光荣而艰巨的任务就是——打鼹鼠!

    题目描述

    鼹鼠一共在仓库中打了n个洞(用1至n编号),在这n个洞中,有些洞之间是连通的,你可以花费一定的时间从连通的一个洞口处跑到另一个洞口处,然而有些洞之间由于货物的堆放等原因并不是连通的,也就是你并不能直接从不连通的一个洞口处跑到另一个洞口处。(但所有的连通关系都是双向的)当你在某一时刻正好在某个洞旁时,如果正好这个洞中有一只出现在洞口处,你就可以用手中的武器(一把大锤)消灭这支鼹鼠,当你在某一时刻停留在某个洞穴处并使用大锤时,该洞当前出现的所有鼹鼠都将被消灭。你有t秒的时间来进行消灭鼹鼠的战斗,你也知道在这t秒内鼹鼠每次出现的时间和位置。那么,你最多能消灭多少只鼹鼠呢?为了尽可能多的消灭鼹鼠,dd_engi为你提供了一种超级武器:如果你在某个特定时刻在某个洞口处使用这个超级武器的话,那么这个洞以及与它直接有边相连的所有洞中此刻出现的鼹鼠都会被消灭掉。然而,这个超级武器只能使用一次。你需要编程求出的就是:用或者不用这个超级武器,你分别能消灭多少只鼹鼠?注意:你可以不用完你所给的时间,而且可以有一些时间你并没有来回跑动而是仅仅停在某个洞的旁边。

    输入输出格式

    输入格式:

    第一行为三个用空格隔开的整数n、m、t,分别表示鼹鼠洞的个数和连通的边数以及你的时间t。 以下m行,每行有三个用空格隔开的整数i、j、k,表示编号i、j的两个鼹鼠洞是双向连通的,从一个运动到另一个需要花费的时间为k。 以下每行有三个用空格隔开的整数,第一个整数表示描述的这些鼹鼠将于第几秒末出现,第二个整数表示描述的这些鼹鼠出现的洞的编号,第三个整数表示这次将会出现的鼹鼠的数量。以三个整数0表示输入的结束。 输入文件的结尾是一个回车/换行符。

    输出格式:

    只需输出两个用空格隔开的整数,分别表示用和不用超级武器能消灭的最多鼹鼠数。最后以一个回车/换行符结尾。

    输入输出样例

    输入样例#1: 复制
    3 2 10
    1 2 1
    2 3 2
    1 1 1
    2 2 2
    3 3 3
    4 1 4
    2 3 3
    4 2 2
    6 1 4
    8 2 3
    10 2 2
    9 1 1
    7 1 5
    3 2 2
    8 1 8
    0 0 0
    
    输出样例#1: 复制
    32 29
    

    说明

    n<=100 t<=1000 dd_engi原创试题

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。