#P11972. [2023年联测]如生存
[2023年联测]如生存
如生存(battle.cpp)
【题目描述】
个房间和 条长廊构成一棵树,是 Bob 闯关时遇到的特殊地形。初始 Bob 在 号房间,成功抵达 号房间即闯关成功。
房间的门并没有上锁,也就是说房间之间都是可以相互抵达的。
每个房间内会有三种分布之一:空,食物,魔物。当 Bob 进入了空房间时,什么也不会发生;进入有食物的房间时可以恢复体力,各种食物可恢复的体力不一定相同;进入有魔物的房间时,需要消耗体力与其战斗,每次战斗所需体力不一定相同。
不幸的是,上一关的数据会继承到这一关,初始时 Bob 的体力为 ,当他的体力小于 时就嗝屁了。
每个房间内的食物只可获取一次,魔物也只需战斗一次;之后可再次经过已处理的房间。
现在 Bob 想要知道自己有没有可能通过这一关,来决定上一关是否需要重开。
【输入格式】
第一行两个正整数,含义如题面所述;
第二行 个整数,第 个整数 表示 号房间内的分布情况: 为空; 为食物,可恢复 点体力; 为魔物,战斗需 点体力。
接下来 行,每行两个正整数 表示 号房间和 号房间之间有一条长廊连接。
【输出格式】
如果 Bob 能通过此关,输出 Yes ,否则输出 No 。
【输入输出样例】
样例输入
7 7
0 -3 2 2 3 -4 0
1 2
2 3
2 4
1 5
5 6
6 7
样例输出
Yes
一种可行的路线:先去 号房间,体力增长为 ;然后去 号房间,体力降为 ;再去 、 号房间,体力增长为 ;再去 号房间,体力降为 ;最后去 号房间,闯关成功。两次前往不相邻房间时,沿树上的路径经过已处理的房间。
样例输入
3 2
0 3 -4
1 3
2 3
样例输出
No
【数据规模及约定】
对于 的测试数据,,,,。原 PDF 的样例 2 把首项写成 ,与本段明确给出的 冲突。本版将该样例首项修正为 ,输出 No 不变;正式数据范围保持原约定。
| Subtask | 的上限 | 特殊性质 | 分值 |
|---|---|---|---|
| 1 | 5 | 无 | 10 |
| 2 | 20 | 20 | |
| 3 | A | 10 | |
| 4 | 无 | 20 | |
| 5 | A | 10 | |
| 6 | B | ||
| 7 | 无 | ||
| 8 |
特殊性质 A:图为一条链。特殊性质 B:所有边满足 。