问题 5647 --动若脱兔5647: 动若脱兔
时间限制: 2 Sec 内存限制: 256 MB
提交: 3 解决: 2
[提交][状态][命题人:]题目描述
在2023年新春之际,去年的生肖老虎与新年的生肖兔子,在玩游戏,游戏名字叫“老虎抓小兔”。
兔子和老虎都在一棵包含 n 个节点的树上,节点之间有指定长度的边相连。树上共有 1 只老虎,老虎初始在 tiger 点, 有 m 只兔子,第 i 只兔子初始在 rabbit[i] 点。如果老虎和兔子同时在同一个节点或边上,则兔子就被老虎抓到了。
每秒老虎的移动速度为 1 ,可以从所在点沿着边移动 1 单位长度。
兔子的移动速度非常快,为无穷大,即兔子可以沿着树上的边,在 1 秒内快速移动到树上的任意一个节点或边上。但如果沿途遇到了老虎,则会被抓住。
当老虎抓完所有兔子时,游戏结束。老虎想让游戏时间尽可能短,兔子想让游戏时间尽可能长,双方均以最优策略行动。
老虎想要尽快抓完所有兔子,兔子想要尽可能晚的使得所有被老虎抓到。
如果所有兔子均能被老虎抓到,则输出所需时间,否则输出 "Goodbye 2022" 。
输入
第一行包含一个正整数 n (1≤n≤50) ,表示树的节点树。
接下来 n-1 行,每行包含两个整数 u,v,v (1≤u,v≤n,1≤w≤50),表示节点 u 与节点 v 之间有长度为 w 的边。
接下来一行,包含一个整数 tiger ,表示老虎初始所在位置。
接下来一行,包含一个整数 m ,表示兔子数量。
最后一行,包含 m 个整数 rabbit[1],rabbit[2],...,rabbit[m] (1≤rabbit[i]≤n,rabbit[i]≠tiger) ,表示兔子所在位置。
输出
如果所有兔子均能被老虎抓到,则输出所需时间,否则输出 "Goodbye 2022" 。
提示
在第一组样例中,最优情况之一如下所示:
2号兔子移动到顶点3, 4号兔子移动到顶点4。老虎来到顶点4,抓住了两个兔子。之后,兔子 1 移动到顶点 2 。老虎去顶点 3 抓兔子 2 ,然后去顶点 2 抓剩下的兔子。
来源
[提交][状态]