最短路径问题

2013年11月7日2,2230

题目描述

平面上有 n 个点(n<=100),每个点的坐标均在-10000~10000 之间。其中的一些点之间有连线 。若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离 。现在的任务是找出从一点到另一点之间的最短路径 。

输入

 输入共 n+m+3 行,其中:
第一行为整数 n。
第 2 行到第 n+1 行    (共 n 行 ),每行两个整数 x 和 y,描述了一个点的坐标。
第 n+2 行为一个整数 m,表示图中连线 的个数。
此后的 m 行(m<=1000),每行描述一条连线,由两个整数 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

代码