logo AlgoBeat OnlineJudge
登录 注册

#200718. 采购特价商品

内存限制:125 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

《爱与愁的故事第三弹·shopping》第一章。


中山路店山店海,成了购物狂爱与愁大神的“不归之路”。中山路上有 )家店,每家店的坐标均在 之间。其中的 家店之间有通路。若有通路,则表示可以从一家店走到另一家店,通路的距离为两点间的直线距离。现在爱与愁大神要找出从一家店到另一家店之间的最短距离。你能帮爱与愁大神算出吗?

输入格式

行:

第一行:整数

接下来 行:每行两个整数 ,描述了一家店的坐标。

接下来一行:整数

接下来 行:每行描述一条通路,由两个整数 组成,表示第 家店和第 家店之间有通路。

接下来一行:两个整数 ,分别表示原点和目标店。

输出格式

仅一行:一个实数(保留两位小数),表示从 的最短路径长度。

样例

样例输入 1

5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5

样例输出 1

3.41

数据范围与提示

对于 的数据: