问题1315--最短路径

1315: 最短路径

时间限制: 1 Sec  内存限制: 128 MB
提交: 21  解决: 20
[提交] [状态] [讨论版] [命题人:]

题目描述

平面内给出 n 个点,记横坐标最小的点为 A,最大的点为 B,现在Zxd想要知道在每个点经过一次(A 点两次)的情况下从 A 走到 B,再回到 A 的最短路径。但他是个强迫症患者,他有许多奇奇怪怪的要求与限制条件:

1.  A 走到 B 时,只能由横坐标小的点走到大的点。

2.  B 回到 A 时,只能由横坐标大的点走到小的点。

3.  有两个特殊点 b1 b2 b1 0 n-1 的路上,b2 n-1 0 的路上。

请你帮他解决这个问题助他治疗吧!

输入

第一行三个整数 n,b1,b2,( 0 < b1b2 < n-1 b1 <> b2)n 表示点数,从 0 n-1 编号,b1 b2 为两个特殊点的编号。

以下 n 行,每行两个整数 xy 表示该点的坐标(0 <= xy <= 2000),从 0 号点顺序

给出。Doctor Gao为了方便他的治疗,保证所有点横坐标不同,并且已经将给出的点按 x 增序排好了。

输出

仅一行,输出最短路径长度(精确到小数点后面 2 位)

样例输入 Copy

5 1 3
1 3
3 4
4 1
7 5
8 3

样例输出 Copy

18.18

提示

【样例解释】

    最短路径:0->1->4->3->2->0

【数据说明】 

    20%的数据n<=20

    60%的数据n<=300

    100%的数据n<=1000

    对于所有数据x,y,b1,b2如题目描述.

来源/分类