TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3479
  • 题目
  • P3479【2015多校联训2】最短路径
    限制 : 时间限制 : 20000 MS   空间限制 : 265536 KB
    问题描述

    平面内给出 n 个点,记横坐标最小的点为 A,最大的点为 B,现在小 Y 想要知道在 每个点经过一次(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< b1,b2<n-1 且 b1< b2)。
    n 表示点数,从 0 到 n-1 编 号,b1 和 b2 为两个特殊点的编号。
    以下 n 行,每行两个整数 x、y 表示该点的坐标(0<= x,y <= 2000),从 0 号点顺序 给出。
    DoctorGao 为了方便他的治疗,已经将给出的点按 x 增序排好了。

    输出格式

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

    样例输入

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

    样例输出

    18.18

    提示

    【样例解释】 最短路径:0->1->4->3->2->0
    【数据范围】
    20%的数据 n<=20
    60%的数据 n<=300
    100%的数据 n<=1000
    对于所有数据 x,y,b1,b2 如题目描述.


    来源  by BS