luogu#P11046. [蓝桥杯 2024 省 Java B] 星际旅行
[蓝桥杯 2024 省 Java B] 星际旅行
题目背景
备注:原题(Java)时间限制 3.0s,空间限制 512 MB。
题目描述
小明国庆节准备去某星系进行星际旅行,这个星系里一共有 个星球,其中布置了 道双向传送门,第 道传送门可以连接 , 两颗星球( 且任意两颗星球之间最多只有一个传送门)。
他看中了一款 “旅游盲盒”,一共有 个盲盒,第 个盲盒里的旅行方案规定了旅行的起始星球 和最多可以使用传送门的次数 。只要从起始星球出发,使用传送门不超过规定次数能到达的所有星球都可以去旅行。
小明关心在每个方案中有多少个星球可以旅行到。小明只能在这些盲盒里随机选一个购买,他想知道能旅行到的不同星球的数量的期望是多少。
输入格式
输入共 行。
第一行为三个正整数 。
后面 行,每行两个正整数 ,。
后面 行,每行两个整数 ,。
输出格式
输出共一行,一个浮点数(四舍五入保留两位小数)。
3 2 3
1 2
2 3
2 1
2 0
1 1
2.00
提示
【样例解释】
- 第一个盲盒可以旅行到 。
- 第二个盲盒可以旅行到 。
- 第三个盲盒可以旅行到 。
所以期望是 。
【数据范围】
- 对于 的评测用例,保证 。
- 对于 的评测用例,保证 ,,,,。