P3548 最短路径问题
描述
平面上有 个点,每个点的坐标均在之间。其中的一些点之间有连线。
若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
输入
共 行,其中:
第一行为整数 。
第2行到第 行(共 行) ,每行两个整数 和 ,描述了一个点的坐标。
第 行为一个整数 ,表示图中连线的个数。
此后的 行,每行描述一条连线,由两个整数 和 组成,表示第 个点和第 个点之间有连线。
最后一行:两个整数 和,分别表示源点和目标点。
输出
一行,一个实数(保留两位小数),表示从 到 的最短路径长度。
样例输入
样例输出