A1880. 采购特价商品
编程题
普及/提高-
知识点
题目描述
《爱与愁的故事第三弹·shopping》第一章。中山路店山店海，成了购物狂爱与愁大神的“不归之路”。中山路上有 $n$（$n \leq 100$）家店，每家店的坐标均在 $-10000$ 至 $10000$ 之间。其中的 $m$ 家店之间有通路。若有通路，则表示可以从一家店走到另一家店，通路的距离为两点间的直线距离。现在爱与愁大神要找出从一家店到另一家店之间的最短距离。你能帮爱与愁大神算出吗？
输入格式
共 $n+m+3$ 行：
第一行：整数 $n$。
接下来 $n$ 行：每行两个整数 $x$ 和 $y$，描述了一家店的坐标。
接下来一行：整数 $m$。
接下来 $m$ 行：每行描述一条通路，由两个整数 $i$ 和 $j$ 组成，表示第 $i$ 家店和第 $j$ 家店之间有通路。
接下来一行：两个整数 $s$ 和 $t$，分别表示原点和目标店。
第一行：整数 $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$。