3058. 【例4-1】最短路径问题 标准IO
时间限制:1000 MS 内存限制:64 MB    算法评级:    状态:

【题目描述】

平面上有 $ n $ 个点( $ n<=100 $ ),每个点的坐标均在 $ -10000 \sim 10000 $ 之间。

其中的一些点之间有连线。

若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离。

现在的任务是找出从一点到另一点之间的最短路径。

【输入】

共 $ n+m+3 $ 行,其中:

第一行为整数 $ n $ 。

第 $ 2 $ 行到第 $ n+1 $ 行(共 $ n $ 行) ,每行两个整数 $ x $ 和 $ y $ ,描述了一个点的坐标。

第 $ n+2 $ 行为一个整数 $ m $ ,表示图中连线的个数。

此后的 $ m $ 行,每行描述一条连线,由两个整数 $ 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
代码运行状态:

输出