采购特价商品(Special Offer Shopping)

题目描述

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

中山路店山店海，成了购物狂爱与愁大神的“不归之路”。中山路上有 $n$（$n \leq 100$）家店，每家店的坐标均在 $-10000$ 至 $10000$ 之间。其中的 $m$ 家店之间有通路。若有通路，则表示可以从一家店走到另一家店，通路的距离为两点间的直线距离。现在爱与愁大神要找出从一家店到另一家店之间的最短距离。你能帮爱与愁大神算出吗？

输入格式

共 $n+m+3$ 行：

第一行：整数 $n$。

接下来 $n$ 行：每行两个整数 $x$ 和 $y$，描述了一家店的坐标。

接下来一行：整数 $m$。

接下来 $m$ 行：每行描述一条通路，由两个整数 $i$ 和 $j$ 组成，表示第 $i$ 家店和第 $j$ 家店之间有通路。

接下来一行：两个整数 $s$ 和 $t$，分别表示原点和目标店。

输出格式

仅一行：一个实数（保留两位小数），表示从 $s$ 到 $t$ 的最短路径长度。

样例输入 #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

数据范围

对于 $100 \%$ 的数据：$2 \le n \leq 100$，$1 \le i, j, s, t \le n$，$1 \le m \leq 1000$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1100。

测试点分布

出处：原题链接