#P18958. [SEUSA2026] E. 商场逃生(Mall Escape)
[SEUSA2026] E. 商场逃生(Mall Escape)
商场逃生(Mall Escape)
题目描述
商场由一个连通无向简单图表示,有 个房间和 条走廊。你在房间 ,商场出口为房间 ,一只僵尸最初位于出口。
定义房间到出口的距离为它到房间 的最短路边数。
每分钟依次发生:
- 你可以走过一条走廊,到达相邻房间;也可以留在原地。
- 僵尸选择一个到出口的距离严格大于当前房间的相邻房间,并走过去。如果有多个选择,则等概率随机选择;若没有,则留在原地。
每次移动只经过一条走廊。在上述过程的任意时刻,只要你和僵尸位于同一房间,就会被抓住;包括你移动后、僵尸尚未移动时。若你到达出口,且僵尸当时不在那里,则成功逃脱。
你知道整个图、僵尸的起点及移动规则,但无法观察或追踪僵尸后续的位置。
在选择最优逃生策略时,被僵尸抓住的概率最小是多少?
输入格式
第一行两个整数 ,其中 ,。
随后 行,每行两个整数 ,满足 ,表示连接两个房间的双向走廊。任意两个房间之间至多一条走廊,且整个图连通。
输出格式
输出最优策略下被抓住的最小概率。
答案的相对误差不超过 ,或绝对误差不超过 时被接受。答案可能小于 ,允许使用科学计数法。
样例
5 6
1 2
1 3
1 4
2 5
3 5
4 5
0.3333333333333333

图 E.1:样例一。You 表示你的位置,Zombie 表示僵尸的位置,entrance 表示出口。你从房间 出发,僵尸从房间 出发。
你可以立即走到房间 中的任意一个,也可以先等一分钟再走。僵尸有 的概率进入或已经位于这个房间;若没有被抓,下一步即可逃走。等待更久会使僵尸必然到达房间 。
12 15
1 2
2 3
3 4
2 5
3 6
4 7
5 6
6 7
5 8
6 9
7 10
8 9
9 10
10 11
11 12
2.5e-01

图 E.2:样例二。蓝色边框标出房间 和 ,它们可作为最优策略中等待一分钟的位置。
一种最优策略是先走到房间 或 ,等待一分钟,再前往出口。被抓概率为 ;不等待而直接前往出口的被抓概率为 。
来源
2026 ICPC Southeast USA Regional Programming Contest Division 1,题目 E。