A1880 | $采购特价商品$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

《爱与愁的故事第三弹·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

输出 #1

3.41

C++ 编辑器

输入

输出