迷阵突围
描述
Tony老师陷入了坐标系上的一个迷阵,迷阵上有n个点,编号从1到n。Tony在编号为1的位置,他想到编号为n的位置上。Tony当然想尽快到达目的地,但是他总是想得太多,觉得最短的路径可能有风险,所以他会选择第二短的路径(在平坦的路面上曲折前行)。现在Tony知道了n个点的坐标,以及哪些点之间是相连的,他想知道第二短的路径长度是多少。
注意,每条路径上不能重复经过同一个点。
格式
输入
第一行输入两个整数n (1 ≤ n ≤ 200) 和m,表示一共有n个点和m条边。
接下来输入n行,每行输入两个整数xi和yi (-500 ≤ xi、yi ≤ 500),分别表示代表第i个点的坐标。
接下来输入m行,每行输入两个整数pj和qj (1 ≤ pi、qi ≤ n)表示点pj和点qj之间相连。
输出
输出一行,输出包含一个数,表示第二短的路径长度(小数点后面保留两位),如果第一短路径有多条,则答案就是第一最短路径的长度;如果第二最短路径不存在,则输出−1。
格式
输入
3 3
1 1
2 2
3 2
1 2
2 3
1 3
输出
2.41
信息
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 4
- 已通过
- 2
- 通过率
- 50%
- 上传者