#P18958. [SEUSA2026] E. 商场逃生(Mall Escape)

[SEUSA2026] E. 商场逃生(Mall Escape)

商场逃生(Mall Escape)

题目描述

商场由一个连通无向简单图表示,有 nn 个房间和 ee 条走廊。你在房间 11,商场出口为房间 nn,一只僵尸最初位于出口。

定义房间到出口的距离为它到房间 nn 的最短路边数。

每分钟依次发生:

  1. 你可以走过一条走廊,到达相邻房间;也可以留在原地。
  2. 僵尸选择一个到出口的距离严格大于当前房间的相邻房间,并走过去。如果有多个选择,则等概率随机选择;若没有,则留在原地。

每次移动只经过一条走廊。在上述过程的任意时刻,只要你和僵尸位于同一房间,就会被抓住;包括你移动后、僵尸尚未移动时。若你到达出口,且僵尸当时不在那里,则成功逃脱。

你知道整个图、僵尸的起点及移动规则,但无法观察或追踪僵尸后续的位置。

在选择最优逃生策略时,被僵尸抓住的概率最小是多少?

输入格式

第一行两个整数 n,en,e,其中 2≤n≤5×1052\le n\le5\times10^5,n−1≤e≤5×105n-1\le e\le5\times10^5。

随后 ee 行,每行两个整数 a,ba,b,满足 1≤a<b≤n1\le a<b\le n,表示连接两个房间的双向走廊。任意两个房间之间至多一条走廊,且整个图连通。

输出格式

输出最优策略下被抓住的最小概率。

答案的相对误差不超过 10−610^{-6},或绝对误差不超过 10−20010^{-200} 时被接受。答案可能小于 10−20010^{-200},允许使用科学计数法。

样例

5 6
1 2
1 3
1 4
2 5
3 5
4 5
0.3333333333333333

样例一中的房间与走廊

图 E.1:样例一。You 表示你的位置,Zombie 表示僵尸的位置,entrance 表示出口。你从房间 11 出发,僵尸从房间 55 出发。

你可以立即走到房间 2,3,42,3,4 中的任意一个,也可以先等一分钟再走。僵尸有 1/31/3 的概率进入或已经位于这个房间;若没有被抓,下一步即可逃走。等待更久会使僵尸必然到达房间 11。

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:样例二。蓝色边框标出房间 44 和 88,它们可作为最优策略中等待一分钟的位置。

一种最优策略是先走到房间 44 或 88,等待一分钟,再前往出口。被抓概率为 1/41/4;不等待而直接前往出口的被抓概率为 1/21/2。

来源

2026 ICPC Southeast USA Regional Programming Contest Division 1,题目 E。

官方资料页 · 原题。中文根据用户提供的官方题面重新整理;全部测试数据来自赛事官方公开的数据包。