lxy 的爬塔游戏
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
lxy 最近喜欢上玩一个 `爬塔游戏`，在这个游戏中共有 $n$ 个 `塔` 编号分别为 $1 \sim n$,而且每座塔都有自己的坐标 $(x_i,y_i)$
塔和塔之间存在一些双向路径，允许玩家从第座塔 $i$ 移动到第 $j$ 座塔。
如果第 $i$ 座塔和第 $j$ 座塔之间存在路径，那么这条路径的长度即为 $\sqrt{(x_i -x_j)^2+(y_i -y_j)^2}$
玩家的移动速度是 $v$，他通过一条长度为 $dis$ 的路径需要花费的时间为 $dis / v$
而游戏允许玩家进行跳跃的操作，允许玩家从第 $i$ 个塔垂直向下跳跃到另一个塔，也就是说对于两座塔 $i,j$，如果 $x_i = x_j$ 且 $y_i > y_j$ 则允许玩家从第 $i$ 座塔跳跃到第 $j$ 座塔（允许过程中穿过其他路径和塔），所花费的时间满足自由落体公式：$\sqrt{(y_i - y_j) * 2 / g}$，这里的 $g$ 取 $10$
现在 lxy 需要从 $1$ 号塔移动到 $n$ 号塔，他最少需要花费多少时间？
输入格式
输入第一行包含两个整数 $n,v$ 表示有 $n$ 座塔，玩家的移动速度是 $v$
接下来 $n$ 行，每行包含三个整数 $x_i,y_i,u_i$，分别表示第 $i$ 个点的坐标是 $(x_i,y_i)$ ，以及第 $i$ 座塔和第 $u_i$ 座塔之间存在路径，若 $u_i = 0$ 则表示这条边不存在
对于 $40\%$ 的数据，$1 \leq n \leq 10, 1 \leq v \leq 10, 0 \leq x_i,y_i \leq 100$
对于 $100\%$ 的数据，$1 \leq n \leq 100, 1 \leq v \leq 10, 0 \leq x_i,y_i \leq 100$
输出格式
输出仅包含一行，表示 lxy 需要从 $1$ 号塔移动到 $n$ 号塔最少需要花费的时间（保留两位小数）
样例
9 1
5 0 0
5 5 1
6 5 2
7 6 2
6 9 2
3 6 2
4 5 2
3 2 7
7 2 38.13
20230422提高组集训
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-4-22 17:15
- 结束于
- 2023-5-2 17:15
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 9
