2432: [C++一本通-图论算法]例4-1 最短路径问题short
Memory Limit：128 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：192
Solved：87
Description
平面上有ｎ个点（ｎ＜＝１００），每个点的坐标均在－１００００～１００００之间，其中的一些点之间有连线。
若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
Input
共ｎ＋ｍ＋３行。
第一行：整数ｎ
第２行到第ｎ＋１行（共ｎ行），每行两个整数ｘ和ｙ，描述一个点的坐标。
第ｎ＋２行为一个整数ｍ，表示图中连线的个数。
此后的ｍ行，每行描述一条连线，由两个整数ｉ和ｊ组成，表示第ｉ个点和第ｊ个点之间有连线。
最后一行：两个整数ｓ和ｔ，分别表示源点和目标点。两个数之间用一个空格隔开。
Output
仅一行，一个实数（保留两位小数），表示从ｓ到ｔ的最短路径长度。
Sample Input Copy
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5Sample Output Copy
3.41