P1751 贪吃虫

    • 7通过
    • 68提交
  • 题目提供者 litc
  • 评测方式 云端评测
  • 标签 图论 搜索 模拟 深度优先搜索,DFS 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    我们都知道一个很著名的游戏——贪吃蛇。它的一大特点是当前一个食物被吃掉后,后一个食物才会出现。今天我们要做的另一个游戏——贪吃虫也很类似。

    题目描述

    贪吃虫有k条,在一棵有n个节点的树上,每只虫子都在不同的节点上。第一个食物到来时,所有的k只虫会从它们当前的位置出发,前往食物的位置。它们的移动遵循如下规则:

    • 这棵树上的任何两个节点之间有且仅有一条路,所有的贪吃虫沿着唯一的路径前往食物所在的位置。

    • 如果有一只贪吃虫到达了食物所在的位置,食物马上就被吃掉了

    • 如果有另外一只贪吃虫在某一只贪吃虫通往食物的道路上,那么距离食物较远的那只虫子会停止移动,停留在当前的节点上

    • 如果有多只虫子尝试进入同一个节点,只有编号最小的虫子能够到达,其它的贪吃虫停留在它们当前的位置上

    • 吃掉食物的那只虫子会停留在食物的位置上

    • 食物被吃掉之后会出现在树上的另外一个节点上。这时所有的贪吃虫会重新出发,尝试再一次吃掉食物。为了简化过程,我们假设从一个节点移动到相邻的节点需要花费一个单位时间。

    输入输出格式

    输入格式:

    第 1 行: 一个整数n,表示树上的节点个数(1<=n<=5000)

    第 2..N 行: 第i+1 行包含了一个两个整数: A_i, B_i,表示从节点A_i到节点

    B_i 有一条边直接相连。

    第 N+1 行: 有一个整数k,表示树上贪吃虫的个数(1<=k<=1000, k<=n)

    第 N+2..N+1+k 行: 第N+1+i 行有一个整数P_i,表示第i 只贪吃虫开始时的位置,任何两只贪吃虫的初始位置不相同

    第 N+2+k 行:有一个整数h,表示食物一共在树上出现了多少次。(1<=h<=500)

    接下来的h 行,每行一个整数,表示食物依次出现的位置。

    输出格式:

    输出一共包含k 行,第i 行有两个整数C_i 和D_i。分别表示第i只贪吃虫最终停留的位置和这只贪吃虫吃到食物的次数。

    输入输出样例

    输入样例#1: 复制
    4
    1 2
    1 3
    2 4
    2
    1
    2
    2
    2
    4
    输出样例#1: 复制
    1 0
    4 2
    

    说明

    1 0 4 2

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