1287: 最短路径问题
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：596
解决：251
题目描述
平面上有n个点（n<=100）,每个点的坐标均在－10000～10000之间，其中的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的之间距离。现在的任务是找出一点到另一点之间的最短路径。
输入
输入共有n＋m＋3行，其中：
第一行为整数n
第2行到第n＋1行（共n行），每行两个整数x和y，描述了一个点的坐标（以一个空格分隔）。
第n＋2行为一个整数m，表示图中连线的个数。
此后的m行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。
最后一行：两个整数s和t，分别表示源点和目标点。
第一行为整数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提示
本道题分别用以下3种算法来完成：
Floyd-Warshall算法
Dijkstra算法
Bellman-Ford算法
最短路算法模板
https://www.acwing.com/blog/content/462/
最短路笔记（2）Dijkstra堆优化版 (手写堆)