2390: Luffy

内存限制:64 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:3 解决:1

题目描述

平面内给出n个点,记横坐标最小的点为A,最大的点为B,现在要求在每个点经过一次(A点两次)的情况下从A走到B,再回到A的最短路径。 限制条件为:

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

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

3. 有两个特殊点b1b2b10n-1的路上,b2n-10的路上。

 

输入

第一行三个整数n,b1,b2,(4 <= n <= 100, 0 < b1b2 < n-1 b1 <> b2)n表示点数,从0n-1编号,b1b2为两个特殊点的编号。 以下n行,每行两个整数xy表示该点的坐标(0 <= xy <= 2000),从0号点顺序给出,且x为增序。

 

输出

第一行输出最短路径长度(精确到小数点后面2位);第二行输出该路径,每两个数之间有且仅有1个空格。保证答案唯一。

 

样例输入 复制

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

样例输出 复制

18.18 
0 1 4 3 2 0