无意识之外的捉迷藏

题目背景

###(五)心与心的对话 旧都还在下着雪。 不知道走了多远的路,已经远离街市了。 眼前隐隐约约能看到一座巨大的宫殿。 那就是,地灵殿吗? 心里突然紧张了起来。 这里住着旧地狱最可怕的觉妖怪。 古明地觉,她拥有读心的能力。人类,妖怪,甚至是怨灵,站在她面前的时候都如同赤身裸体,没有任何秘密可言。而且,听说在战斗中,她还会使用催眠术不断激起对手内心深处的恐怖回忆,从心灵上打垮对手。这样的妖怪自然会被人讨厌啦。 不过,此次地底之旅可不能因为要遇到可怕的妖怪而就此结束。 咚咚咚,敲了敲地灵殿的大门。 “来客吗,真是少见呢。” 眼前,站着一个少女,穿着蓝色的衣服,粉红色的裙子,头发也是粉红色的。 在她的胸前,悬着一只红色的大眼睛,通过眼睛周围的六根管子连接着身体。 她看起来很温柔的样子,完全不像听说的那样恐怖。 “来地底旅行的外面世界的人类吗?真是非常少见呢,居然找到了这里” “看起来没有别的想法,就是想来转转呢,那就进来吧” 走进大门。 不愧是地灵”殿”,真的是好大的一个宫殿,桃红色和黑色相间的地板,印有花纹的窗户。 眼前是一组很宽的台阶,通向二楼,然后分成左右两个通道。 “很漂亮吧,这里空间大,宠物们都很喜欢呢。” 就这样,我跟着觉进入了她工作的房间,我们坐在沙发上聊了很久,虽然我很少说话。 在聊天的过程中,我了解到她还有一个妹妹古明地恋,由于不愿让别人因为自己会读心而讨厌自己,闭上了觉之瞳。觉为了开导妹妹,经常和宠物陪着她玩。 地灵殿,觉和妹妹,宠物们,一直在过着平静又温馨的生活。 “既然来这里了,就和我们一起玩吧。”觉邀请我们参与她们的游戏。 地底的妖怪会玩怎样的游戏呢? 于是,就这样,我就答应参与觉和恋的“无意识的捉迷藏”了。 说是”捉迷藏”,其实和普通的捉迷藏区别很大,更类似于”捉人游戏”。 就是觉和恋一开始分别站在两个地方,觉要捉到恋就算赢了。 但为什么又说是”捉迷藏”呢? 原来恋恋可以无意识地行动,也就是可以让周围人在潜意识里忽略她的存在,类似隐身,但又不是隐身。真是有趣的能力呢,是不是闭上了觉之瞳的缘故? 我们玩得很开心。有时无意识碰到了恋恋的手,还吓了一跳呢。 一段时间后,姐妹俩累了,觉还有工作要处理,就先回去了。 宠物们似乎意犹未尽,她们还想继续。 “可是在这个旧地狱啊,除了主人的妹妹恋以外,哪里又有妖怪能够操纵无意识呢? 算了,干脆玩普通的捉人游戏吧。”阿燐提议道。 于是宠物们很快又忘我地投入了”无意识之外的捉迷藏”中。 不知什么时候,我感到背后一凉,回过头一看,原来是恋恋。 我们就这样站在这里看着宠物们玩。 虽然不知道为什么能耐心地看那么长时间,但几个小时过去了,我们依然站在这里。 恋恋好像有一些疑问,在经过简单的交流后,我把她的疑问做了一个总结。 (见题目描述) 这个问题对无意识的恋恋来说果然无法解决啊。 能和姐妹俩聊得这么开心,真是很感激呢,那就尽自己的努力思考一下这个问题吧。 (后续剧情见题解,接下来请看T4)

题目描述

###问题摘要: 在一个有向无环图上,阿燐和阿空第0个时刻分别站在编号为$s_r$,$s_k$的节点,二人都知道双方的初始位置,对地图完全了解。 从第1个时刻起,每个时刻阿燐和阿空都可以选择站着不动,也可以选择移动到相邻的节点,二人每时刻的移动是同时开始的,并且不能中途改变方向。 阿燐被阿空捉住时,游戏立即结束。如果阿空一直没有捉住阿燐,第$t$个时刻结束后两人就不能再继续移动了,游戏将在第$t+1$个时刻结束。 阿空的目的是尽快捉住阿燐(捉住的定义是与阿燐同一时刻站在同一节点),而阿燐的目的是尽可能更长时间不被阿空捉住。具体而言,若一场游戏进行了$t_0$时刻,阿燐的得分是$t_0$,阿空的得分是$-t_0$,双方都希望自己得分(或得分的期望值)更高。 我们认为在这个过程中阿燐和阿空随时都能知道对方的位置。两人在第$t$个时刻不能看出第$t+1$个时刻对方要走到哪里。 恋恋想知道,在双方最优决策的情况下,游戏结束时刻的期望值是多少。

输入输出格式

输入格式


第一行5个整数$n$,$m$,$s_r$,$s_k$,$t$,用空格隔开,下同。 $n$表示地图点数,$m$表示边数。 接下来$m$行,每行两个整数$a$,$b$,表示从$a$到$b$有一条单向边(不存在重边)。

输出格式


一个实数,四舍五入保留3位小数,表示游戏结束时刻的期望值。 你的答案必须和标准答案完全相同才算正确。

输入输出样例

输入样例 #1

3 2 1 2 10
1 3
2 3

输出样例 #1

11.000

输入样例 #2

6 8 2 1 2
1 2
1 3
1 5
2 3
3 5
5 6
6 4
2 4

输出样例 #2

2.333

说明

###样例解释: 样例1:阿燐只要一直不动,阿空在前$t$单位时间内就无法抓到阿燐,答案为$t+1$,即```11.000``` 样例2:无可奉告 ###数据范围: 对于30%的数据 $n\leqslant3$,捆绑测试 对于100%的数据 $n,t\leqslant20$,前40%的数据和后30%的数据分别捆绑测试 ###提示: 本题主要考察你能否使用正确的方法算出答案,对算法运行耗时要求不高。 by orangebird