老太太经常去市场抢鸡蛋。市场里有 n(n ≤ 100)个摊位,每个摊位的坐标均在 -10000 至 10000 之间。市场中有 m 条路连接摊位。如果有一条路,则表示可以从一个摊位走到另一个摊位,路的距离为两点间的直线距离。现在老太太要找出从一个摊位到另一个摊位之间的最短距离。你能帮老太太算出吗?
共 n+m+3 行:
第一行:整数 n。
接下来 n 行:每行两个整数 x 和 y,描述了一家店的坐标。
接下来一行:整数 m。
接下来 m 行:每行描述一条通路,由两个整数 i 和 j 组成,表示第 i 家店和第 j 家店之间有通路。
接下来一行:两个整数 s 和 t,分别表示原点和目标店。
仅一行:一个实数(保留两位小数),表示从 s 到 t 的最短路径长度。
5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5
3.41
对于 100 \% 的数据:2 \le n \leq 100,1 \le i, j, s, t \le n,1 \le m \leq 1000。