最短路径问题

题目描述

平面有n个点和若干无向连线，连线权值为两端点的欧几里得距离。点坐标可以相同，此时连线长度为0。求指定s到t的最短路长度。

输入

第一行n，1≤n≤100；随后n行整数坐标x,y，均在-10000..10000内。下一行m，0≤m≤n(n-1)/2；随后m行不同的无向边u,v，u≠v。最后一行s,t，1≤s,t≤n，允许s=t。

输出

无路输出-1.00。否则输出一个非负实数，保留两位小数。以精确最短长度四舍五入至两位后的数值为基准，允许绝对误差不超过0.01；答案采用数值特判。

输入样例

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